Understanding Conflict-Free FIFO in Computer Architecture Labs
Exploring the concept of Conflict-Free FIFO in computer architecture labs, this content delves into the grading of FIFO designs and the challenges faced in creating conflict-free implementations. It discusses the typical use of FIFOs for enqueuing, dequeuing, and clearing operations, emphasizing the importance of avoiding scheduling conflicts in these processes. The content also covers scenarios of sequential and concurrent FIFO executions, highlighting the complexity of interactions during operations such as clear and enqueue. Through detailed explanations and visual aids, it provides insights into optimizing FIFO designs for efficient data processing.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Constructive Computer Architecture: Lab Comments & RISCV 10/3/2024 http://csg.csail.mit.edu/6.175 L14-1
Notes Inelastic VS Elastic The FIFO lab has been graded Good job on the conflicting, pipeline, and bypass FIFOs Difficulties in the Conflict-Free FIFO with clear. 10/3/2024 http://csg.csail.mit.edu/6.175 L14-2
What is a Conflict-Free FIFO? Is it a FIFO with a conflict matrix filled with CFs? Not really... Is it a FIFO that, in its typical use, doesn t impose any more conflicts than necessary? Yes! 10/3/2024 http://csg.csail.mit.edu/6.175 L14-3
Typical FIFO use Enqueuing: check notFull and call enq(x) Dequeuing: check notEmpty and call first and deq Clearing: call clear These are the methods that commonly appear in the same rule A CF FIFO says enqueuing and dequeuing rules will have no scheduling conflict imposed by the FIFO. {notFull, enq} CF {notEmpty, first, deq} 10/3/2024 http://csg.csail.mit.edu/6.175 L14-4
Sequential FIFO Execution Assume FIFO is empty initially How many clock cycles does this take? Should that change the answer to these questions? 1. enq(1) 2. first 3. deq 4. enq(2) 5. clear 6. enq(3) 7. enq(4) 8. first 9. deq What is the state of the fifo here? What does first return? How many elements are in the FIFO at the end? 10/3/2024 http://csg.csail.mit.edu/6.175 L14-5
Concurrent FIFO Execution With Clock Cycles Clock cycle boundary 1. enq(1) 2. first 3. deq 4. enq(2) 5. clear 6. enq(3) 7. enq(4) 8. first 9. deq 1. enq(1) 2. first 3. deq 4. enq(2) 5. clear 6. enq(3) 7. enq(4) 8. first 9. deq If these are both valid executions for a given FIFO, they should produce the same results. 10/3/2024 http://csg.csail.mit.edu/6.175 L14-6
Concurrent FIFO Execution Clear-Enq Interactions 1. enq(1) 2. first 3. deq 4. enq(2) 5. clear 6. enq(3) 7. enq(4) 8. first 9. deq 1. enq(1) 2. first 3. deq 4. enq(2) 5. clear 6. enq(3) 7. enq(4) 8. first 9. deq What should clear and enq do when they happen in the same cycle? If both executions are valid, then the action has to be dynamic based on the order. 10/3/2024 http://csg.csail.mit.edu/6.175 L14-7
Can we detect the order of methods firing? In order for a method to know if it fired after another method fired, it has to always be scheduled after that method If you want two methods to be able to tell if either of them came after the other, they have to conflict They will never fire in the same cycle making this problem of who fired first trivial... 10/3/2024 http://csg.csail.mit.edu/6.175 L14-8
Concurrent FIFO Execution CF FIFO solution Invalid Execution 1. enq(1) 2. first 3. deq 4. enq(2) 5. clear 6. enq(3) 7. enq(4) 8. first 9. deq 1. enq(1) 2. first 3. deq 4. enq(2) 5. clear 6. enq(3) 7. enq(4) 8. first 9. deq Force enq < clear 10/3/2024 http://csg.csail.mit.edu/6.175 L14-9
What does a CF FIFO do? It allows the most flexible scheduling constraints possible while still requiring all valid concurrent executions to match the expected result from sequential execution. That is why {enq, deq} < clear and not {enq, deq} CF clear 10/3/2024 http://csg.csail.mit.edu/6.175 L14-10
What about the canonicalize rule? What happens if you have: {enq, deq} < canonicalize < clear If deq and clear occur in the same rule, that rule conflicts with canonicalize. This may or may not be a problem depending on the exact use. {enq, deq} < clear < canonicalize canonicalize can always fire at the end of the cycle independent of how enq, deq, and clear are used in rules 10/3/2024 http://csg.csail.mit.edu/6.175 L14-11
RISCV tutorial 10/3/2024 http://csg.csail.mit.edu/6.175 L14-12
Introduction In lab 5, you will be making modifications to an existing, functional, RISCV processor How do you know if your processor is working? You will run an existing suite of C and assembly software test benches on your processor What could go wrong? Software and Hardware How will you debug this? 10/3/2024 http://csg.csail.mit.edu/6.175 L14-13
Running RISCV 10/3/2024 http://csg.csail.mit.edu/6.175 L14-14
Connectal Testbench Interface tb C++ mkProc BSV COP PC Core iMem dMem 10/3/2024 http://csg.csail.mit.edu/6.175 L14-15
Loading Programs tb C++ mkProc BSV COP PC Core iMem test.vmh dMem 10/3/2024 http://csg.csail.mit.edu/6.175 L14-16
Starting the Processor tb C++ mkProc BSV COP Starting PC 0x1000 PC Core iMem dMem 10/3/2024 http://csg.csail.mit.edu/6.175 L14-17
Printing to Console tb C++ mkProc BSV Get write to reg 18 and 19 18: Print int x 19: Print char x COP PC Core iMem dMem 10/3/2024 http://csg.csail.mit.edu/6.175 L14-18
Finishing Program tb C++ mkProc BSV Get write to csr x == 0: PASSED x != 0: FAILED x COP PC Core iMem dMem 10/3/2024 http://csg.csail.mit.edu/6.175 L14-19
Ballad in the code Compilation of software Life of a print statement Software side Hardware side Example of debugging 10/3/2024 http://csg.csail.mit.edu/6.175 L14-20
Programming RISCV 10/3/2024 http://csg.csail.mit.edu/6.175 L14-21
Tooling for RISCV software How to compile your own C How to assemble How to disassemble 10/3/2024 http://csg.csail.mit.edu/6.175 L14-22
C Programs Start code Jumps to main. Print library Can print chars, ints, and strings No malloc You can write one! 10/3/2024 http://csg.csail.mit.edu/6.175 L14-23
Functional Programming 10/3/2024 http://csg.csail.mit.edu/6.175 L14-24
Functional Programming Basics of functional programming emphasizes pure functions pure functions have no side effects Avoids mutable data (mutable = mutate + able) Example: Instead of sorting a list in place, create a function called sort that takes in a list and returns a new list that is sorted Functions are typically first-class objects Functions can take in functions as arguments and return them 10/3/2024 http://csg.csail.mit.edu/6.175 L14-25
Intro to Haskell A functional programming language Function type definition: addFive :: Integer -> Integer The function addFive takes in an integer and produces an integer Function definition: addFive x = x + 5 The function addFive applied to a variable x produces x + 5 10/3/2024 http://csg.csail.mit.edu/6.175 L14-26
Intro to Haskell A functional programming language Function type definition: add :: Integer -> Integer -> Integer The function add takes in two integers and produces an integer Function definition: add x y = x + y The function add applied to variable x and y produces x + y addFive = add 5 10/3/2024 http://csg.csail.mit.edu/6.175 L14-27
Intro to Haskell A functional programming language The add function is actually curried It is a function on one Integer that returns (a function on one Integer that returns an Integer) add :: Integer -> (Integer -> Integer) add x :: Integer -> Integer Like add(x)(y) instead of add(x,y) BSV supports currying too 10/3/2024 http://csg.csail.mit.edu/6.175 L14-28
