MO601 / MC973 - Computer Architecture II

22/12Final grids.
18/12Exam 2 grids.
12/12Project 4 deadline postponed to Dec. 15th.
11/12Project 2 grids.
05/12Project 1 grids.
20/10Class for 21 / oct canceled. Project 2 postponed to 23 / oct (end of day).
16/10Exam 1 grids.
10/08Lectures will start on Monday, 22nd.
July 22thImportant dates in the school calendar: Graduate and Graduate programs.

This course will cover tools and methodologies for Computer Architecture research including modern simulators, benchmarks for single / multi-colors and clusters. We will study recent papers on the area and how they model pipelines, caches, execution engines, power evaluation, etc.

The recommended bibliography contains:

  • Microarchitecture Processor: An Implementation Perspective. Antonio González, Fernando Latorre and Grigorios Magklis. Synthesis Lectures on Computer Architecture. Morgan && Claypool Publishers.
  • Modern Processor Design: Fundamentals of Superscalar Processors. John Paul Shen, Mikko H. Lipasti. Waveland Press. 2013.
  • Papers from Top Computer Architecture Conferences

Videos about virtual memory (Contributed by Alberto Oliveira): 1, 2, 3, 4.

2 Written exams: 60% of final grade (30% each).

Practical Projects: 40% of final grade.

Grid ranges: A for grade> 8.4, B for grade> 6.9, C for grade> 4.9, D for grade <5.

Any unethical behavior related to the evaluation process will result in failing the course with the lowest possible grade. Every assignment is an individual assignment unless otherwise mentioned. Students are not expected to see each other solutions to the assignments.

Exercises provided by Marcus Angeloni

  1. What are benchmarks?
  2. What is the difference between computer architecture and microarchitecture?
  3. What are the most common dimensions for classifying processor microarchitectures? Explain three of them.
  4. What is the difference between multicore and multithreaded processors?
  5. What are the seven stages of a microprocessor pipeline?
  6. How big would cache memory be on an ideal system? Why?
  7. What is the difference between first-level cache and other levels?
  8. What are the motivations for using virtual addressing?
  9. What is virtual aliasing?
  10. What is a page?
  11. What is TLB and what is it for?
  12. What is the difference between parallel tag and serial tag in the context of data array access?
  13. What are the types of misses in the context of loockup-free caches?
  14. What is the difference between MSHRs explicitly addressed and implicitly addressed?
  15. What is the difference between multiport and multibank caches?
  16. What is the responsibility of the instruction fetch unit?
  17. How does branch prediction work and what is it for?
  18. What is the difference between BTB and RAS?
  19. What is the difference between conventional cache and trace cache?
  20. What is the difference between static and dynamic prediction?
  21. How do you choose which branch predictor to use?
  22. What is the purpose of the instruction decoder? What does he identify?
  23. What is the difference between RISC and CISC?
  24. How big in bytes can an instruction take on an x86 architecture?
  25. What are micro-operations and what are they for?
  26. What is the role of the allocation phase in the microprocessor pipeline?
  27. Why is register renaming necessary?
  28. What is the main limitation on the number of registers on the processor?
  29. What is the reorder buffer for?
  30. What is the difference between rename buffer and reorder buffer?
  31. How does the merged register file strategy work?
  32. What are the strategies for when register values ​​are read? What are the advantages of each of them?
  33. What is the idea of ​​the SimPoints approach? What are the benefits?
  34. What are phases of a program?
  35. What are SimPoints?

other exercises

  1. What are the main limitations on the number of instructions executed in parallel?
  2. Design a piece of C code containing a function call, a loop, and an if statement. Show where should be the branches in the assembly code. For each branch, explain how easy / difficult they can be predicted.
  3. Show a piece of assembly code containing at least one WAR, RAR, WAW, RAW dependencies. What will happen to this code after register renaming?
  4. Show an example (piece of code) of a Trace Cache performing better than a conventional cache. How good is this cache in this example?
  5. How can you decode multiple x86 instructions from a block of bytes retrieved from the instruction cache?
  6. Considering a sequence of 10 instructions to be fetched from memory in a scalar processor. Also consider that this processor has a branch predictor. How many times will the branch predictor hardware be accessed? Why?

Exercises provided by Marcus Angeloni

  1. What is the purpose of the dispatch stage?
  2. What is the difference between in-order and out-of-order dispatch?
  3. How does scoreboarding work?
  4. How does the dispatch queue work when operands are read before dispatch?
  5. What are and what do the different dispatch queue events do?
  6. What is the main difference between reading after dispatch and before dispatch?
  7. How does the emission queue work when the operands are read after dispatch?
  8. How do the different types of memory disambiguation work?
  9. What are the concepts behind a distributed dispatch queue?
  10. What are the matrices of indeterminacy and dependency for?
  11. Why is speculating on memory access considered so critical?
  12. What are the differences between conservative and speculative wakeup?
  13. What is the purpose of the execution stage?
  14. What are the most common execution units?
  15. What is the bypassing network?
  16. Why are the units of logic and arithmetic in general separated from that of multiplication and division?
  17. How do multiplication and division operations on processors that do not implement these units?
  18. What is the difference between segmented and flat memory models?
  19. What is an effective address?
  20. What is the purpose of the branch unit?
  21. How do SIMD units work? What are its advantages?
  22. Generally how is a SIMD unit composed? What are lanes?
  23. What are bubbles? Can bypassing minimize them?
  24. What are the advantages and disadvantages of bypass?
  25. Why is result bypassing in orderly processors often more complex than out-of-order processors?
  26. What are SRF and what are they for?
  27. How does clustering work?
  28. Name and explain two types of clustering.
  29. Why is a commit stage necessary?
  30. What are the architectural and speculative stages and how are they related?
  31. What is the difference between architectural states based on the Remove Register File and Merged Register File? For what type of processors is it best to use each one?
  32. How is a branch misprediction recovered?
  33. What are the forms of treatment of branch misprediction?
  34. How is an exception recovered?

Exercises provided by Pedro Henrique Amorim

  1. What is the role of the Issue stage?
  2. What are the main issue schemes?
  3. In general how is the in order and out of order schema executed?
  4. What is the role of scoreboarding?
  5. Please briefly comment on how the "in-order" technique works on VLIW processors?
  6. Describe the scenario in which the unified issue queue is assumed.
  7. Describe the scenario in which reservation stations are assumed.
  8. In a read before issue scheme there are several components, comment on the purpose of the following components:
    1. What is the role of the "ctrl info" block in the issue out of order scheme?
    2. What does CAM (Content Address Memory) do?
    3. Arrays called Src1Id and Src2Id?
    4. Blocks V1 and V2?
    5. Blocks R1 and R2?
  9. Describe the following events:
    1. Issue queue allocation.
    2. Wakeup instruction.
    3. Instruction selection.
    4. Issue queue complaint.
  10. Name two reasons that can cause an instruction to stand still in the issue stage.
  11. In the pipeline of a given processor, the Issue stage executes 8 instructions at a time but in the fetch stage it is possible to execute 16 instructions simultaneously, how many instructions will be obtained simultaneously after the commit stage is finished?

Exercises provided by Rafael Junio

  1. How do you calculate the size of a flat page table? Calculate the size of a 64-bit processor flat page table using 4KB pages.
  2. How can a multilevel page table save space compared to a flat page table?
  3. Given a 4-level page table: 64-bit virtual address, 64 kb page size, 8B page entry. Only addresses between 0 and 4GB are used, calculate the size of the flat page table and the 4-level page table due equally.
  4. Calculate the latency of a miss in a virtual to physical address translation considering a 3-level page table. Consider that:
    • 1 cycle to compute the virtual address
    • 1 cycle to access the cache
    • 20 cycles to access memory
    • 90% hit for data
    1. page table is not cached.
    2. page table is cached and has 90% data hit.
  5. How big is a TLB with a 4KB page such that it has the same hit rate as a cache with 32KB in size and 64B in block size?

I will provide office hours after each class. If you need more or alternative time, feel free to schedule by email.

Every assignment is an individual assignment unless otherwise mentioned. Students are not expected to see each other solutions to the assignments.

Project 1

Infrastructure: PIN and SPEC 2006

Tasks:

  1. Install SPEC 2006, run it, understand the runspec script.
  2. Install PIN, run a few examples. Understand how it works.
  3. Use the available pintools to count the number of instructions of each SPEC program.
  4. Create a new pintool and use it in at least 5 SPEC programs.

Report:

  • Create a folder called project1 in your repository
  • Due to Sep 19, 10AM
  • report document. SBC Template🇧🇷 You can choose either English or Portuguese for your report. Maximum of 6 pages containing the count (item 3 above) and the description and result of your pintool. Filename: report.pdf
  • Presentation Document🇧🇷 Create a file called presentation.pdf containing slides for a 5 minute presentation of your project.
  • csv file. include a file results.csv containing the results of the instruction count. This file should contain two columns where the first is the program name and the second is the instruction count. For programs that run more than one time, include the execution number (1, 2, 3) after their names.
  • Source code🇧🇷 Include your source code in the folder src. This folder should contain all code that you created / modified together with scripts to execute and a README.md file explaining dependencies. Your script could rely on environment variables for prerequisites.

Project 2

Infrastructure: PIN, and 10 benchmarks

task:

  • Evaluate Virtual to Physical memory translation for 4KB and 4MB pages.
  • Consider up to 512 TLB entries for instruction and data.
  • Consider 3 or 4 levels page table.
  • Look for benchmarks with large memory footprint.
  • Create one toy benchmark to check your environment.

Report:

  • Create a folder called project2 in your repository
  • Due to 23 / Oct (end of the day)
  • report document. SBC Template🇧🇷 You can choose either English or Portuguese for your report. Maximum of 6 pages containing the count (item 3 above) and the description and result of your pintool. Filename: report.pdf
  • Presentation Document🇧🇷 Create a file called presentation.pdf containing slides for a 5 minute presentation of your project.
  • csv file. include a file results.csv containing your results. For each benchmark, include the following columns: benchmark name (nd input if necessary), total memory access for instructions, total TLB misses for instructions, total page table access for instructions, total memory access for data, total TLB misses for data, total page table access for data.
  • Source code🇧🇷 Include your source code in the folder src. This folder should contain all code that you created / modified together with scripts to execute and a README.md file explaining dependencies. Your script could rely on environment variables for prerequisites.

Project 3

Goal: Reproduce one item (graph, table, etc.) of a pre-selected paper from the last three editions of the following conferences: ISCA, ASPLOS, MICRO, HPCA.

Tasks:

  • Create a folder called project3 in your repository
  • Every Friday, up to 21 / Oct, include the reference to one paper that you preliminary inspected in a file called papers.txt
  • When you feel that you have selected the desired paper, talk to me to reserve it and avoid conflicts. Insert the PDF paper in your repository as paper.pdf and create a short overview of it together with the specification of your task and how you plan to execute it in the following weeks. This presentation should be in a file called presentation1.pdf and you are expected to talk about it for 15 minutes in the classes of 31 / Oct and 04 / Nov.

Report:

  • Create a folder called project3 in your repository
  • Due to Nov / 17 (end of the day)
  • report document. SBC Template🇧🇷 You can choose either English or Portuguese for your report. Maximum of 6 pages containing the count (item 3 above) and the description and result of your pintool. Filename: report.pdf
  • Presentation Document🇧🇷 Create a file called presentation2.pdf containing slides for up to 15 minutes presentation of your project.
  • Source code🇧🇷 Include your source code in the folder src. This folder should contain all code that you created / modified together with scripts to execute and a README.md file explaining dependencies. Your script could rely on environment variables for prerequisites.

selected papers

  • João Paulo Labegalini de Carvalho: Varun Agrawal, Abhiroop Dabral, Tapti Palit, Yongming Shen, and Michael Ferdman. 2015. Architectural Support for Dynamic Linking. In Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages ​​and Operating Systems (ASPLOS '15). ACM, New York, NY, USA, 691-702. DOI: http://dx.doi.org/10.1145/2694344.2694392
  • Gustavo Ciotto Pinton: R. Parihar and MC Huang, "Accelerating decoupled look-ahead via weak dependence removal: A metaheuristic approach," 2014 IEEE 20th International Symposium on High Performance Computer Architecture (HPCA), Orlando, FL, 2014, pp. 662-677.
  • Ciro Ceissler: Shao, Yakun Sophia, et al. "Aladdin: A pre-rtl, power-performance accelerator simulator enabling large design space exploration of customized architectures." 2014 ACM / IEEE 41st International Symposium on Computer Architecture (ISCA). IEEE, 2014.
  • Rafael Junio: FLUSH + RELOAD: A High Resolution, Low Noise, L3 Cache Side-Channel Attack. Usenix Security Simposium 2014.
  • Lucas Prado Melo: Hilton, AD, BC Lee, and Z. Huang. "Decoupling loads for nano-instruction set computers." Proceedings of The 43rd International Symposium on Computer Architecture. 2016.
  • Paulo Henrique Junqueira Amorim: Tri M. Nguyen and David Wentzlaff. 2015. MORC: the manycore-oriented compressed cache. In Proceedings of the 48th International Symposium on Microarchitecture (MICRO-48).
  • Uglaybe Fernandes: Albericio, Jorge, et al. "Wormhole: Wisely predicting multidimensional branches." Proceedings of the 47th Annual IEEE / ACM International Symposium on Microarchitecture. IEEE Computer Society, 2014.
  • Alceu Emanuel Bissoto: Akanksha Jain, Calvin Lin. "Back to the Future: Leveraging Belady's Algorithm for Improved Cache Replacement". Proceedings of The 43rd International Symposium on Computer Architecture (ISCA). 2016.
  • Marcus de Assis Angeloni: S. Bucur, J. Kinder, and G. Candea - "Prototyping symbolic execution engines for interpreted languages". In Proceedings of the 19th International Conference on Architectural Support for Programming Languages ​​and Operating Systems (ASPLOS '14). ACM, New York, NY, USA, 239-254.
  • Rafael Soares: S. Girbal, G. Mouchard, A. Cohen, and O. Temam. DiST: A simple, reliable and scalable method to significantly reduce processor architecture simulation time. In Proceedings of the 2003 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, pages 1–12, June 2003.
  • Alfredo Salvarani: D. Gope and MH Lipasti, "Bias-Free Branch Predictor," 2014 47th Annual IEEE / ACM International Symposium on Microarchitecture, Cambridge, 2014, pp. 521-532.
  • George Araújo: S. Khan, AR Alameldeen, C. Wilkerson, O. Mutluy and DA Jimenezz, "Improving cache performance using read-write partitioning," 2014 IEEE 20th International Symposium on High Performance Computer Architecture (HPCA), Orlando, FL, 2014, pp. 452-463.
  • Paulo Henrique: Eric Rotenberg, Steve Bennett, and James E. Smith. 1996. Trace cache: a low latency approach to high bandwidth instruction fetching. In Proceedings of the 29th annual ACM / IEEE international symposium on Microarchitecture (MICRO 29). IEEE Computer Society, Washington, DC, USA, 24-35.
  • Davi Castro: G. Aşılıoğlu, Z. Jin, M. Köksal, O. Javeri and S. Önder, "LaZy Superscalar," 2015 ACM / IEEE 42nd Annual International Symposium on Computer Architecture (ISCA), Portland, OR, 2015, pp . 260-271.
  • Pedro Tadahiro: The Inner Most Loop Iteration counter: a new dimension in branch history - Andre Seznec (INRIA / IRISA), Joshua San Miguel (University of Toronto), Jorge Albericio (University of Toronto)

Project 4

Goal: Expand an activity of the project 3 paper.

Tasks:

  • Create a folder called project4 in your repository
  • You can explore more configurations, you can make any variation to the algorithm, you can choose other opportunities. You do not need to get better results. You can even work to better explain the official result.

Report:

  • Create a folder called project4 in your repository
  • Due to 12 / Dec (end of the day)
  • report document. SBC Template🇧🇷 You can choose either English or Portuguese for your report. Maximum of 6 pages containing the count (item 3 above) and the description and result of your pintool. Filename: report.pdf
  • Presentation Document🇧🇷 Create a file called presentation.pdf containing slides for up to 15 minutes presentation of your project.
  • Source code🇧🇷 Include your source code in the folder src. This folder should contain all code that you created / modified together with scripts to execute and a README.md file explaining dependencies. Your script could rely on environment variables for prerequisites.
DateTopic
22 / agoIntroduction
26 / agoReading a paper - Project 3 description
29 / agoIntroduction to Microarchitecture
02 / setOverview of Execution Environments
05 / setCaches
09 / setWorktime for Project 1
12 / setWorktime for Project 1
16 / setFetch Unit
19 / setProject 1
23 / setDecodeUnit
26 / setAllocation
30 / setSimPoints
03 / outWorktime for Project 2
07 / outWorktime for Project 2
10 / outReview
14 / outexam 1
17 / outexam 1 resolution
21 / outClass canceled
24 / outProject 2 - Presentation
28 / outHolliday
31 / outProject 3 - Preliminary presentation
04 / NovProject 3 - Preliminary presentation
07 / NovIssue
11 / NovReview Project 3
14 / NovHolliday
18 / NovProject 3 - Presentation
21 / NovProject 3 - Presentation
25 / NovRun
28 / NovCommit
02 / tencache coherence
05 / tenReview
09 / tenHolliday
12 / tenexam 2
16 / tenProject 4