Project 1 – LC-3300 Datapath 1 Requirements Gatekeeper restrictions. • The LC-3300 assembler is written in Python. If you do not have Python 3 or newer installed on your system, you will need to install it before you continue. 2 Project Overview and Description Project 1 is designed to give you a good feel for exactly how a processor works. In Phase 1, you will design a datapath in CircuitSim to implement a supplied instruction set architecture. You will use the datapath as a tool to determine the control signals needed to execute each instruction. In Phases 2 and 3, you are required to build a simple finite state machine (the “control unit”) to control your computer and actually run programs on it. 3 Phase 1 – Implement the DatapathFigure 1: Datapath for the LC-3300 Processor In this phase of the project, you must learn the Instruction Set Architecture (ISA) for the processor we will be implementing. Afterwards, we will implement a complete LC-3300 datapath in CircuitSim using what you have just learned. You must do the following: 1. Learn and understand the LC-3300 ISA. The ISA is fully specified and defined in Appendix A: LC-3300 Instruction Set Architecture. Do not move on until you have fully read and understood the ISA specification. Every single detail will be relevant to implementing your datapath in the next step. 2. Using CircuitSim, implement the LC-3300 datapath. To do this, you will need to use the details of the LC-3300 datapath defined in Appendix A: LC-3300 Instruction Set Architecture. You should model your datapath on Figure 1. 3. Put your name on your CircuitSim data path in a comment box so we know it is your work. 3.1 Hints 3.1.1 Subcircuits CircuitSim enables you to break create reusable components in the form of subcircuits. We highly recommend that you break parts of your design up into subcircuits. At a minimum, you will want to implement your ALU in a subcircuit. The control unit you implement in Phase 2 is another prime candidate for a subcircuit. 3.1.2 Debugging As you build the datapath, you should consider adding functionality that will allow you to operate the whole datapath by hand. This will make testing individual operations quite simple. We suggest your datapath include devices that will allow you to put arbitrary values on the bus and to view the current value of the bus. Feel free to add any additional hardware that will help you understand what is going on. 3.1.3 Memory Addresses Because of CircuitSim limitations, the RAM module is limited to no more than 16 address bits. Therefore, per our ISA, any 32-bit values used as memory addresses will be truncated to 16 bits (with the 16 most significant bits disregarded). If you use the RAM subcircuit we provide, this truncation has already been handled, and you can simply attach the 32-bit value from the MAR (Memory Address Register) to our custom RAM circuit. Otherwise, you will need to truncate the most significant bits of the the address value from the MAR before feeding it into the RAM. 3.1.4 Comparison Logic The “comparison logic” box in Figure 1 is responsible for performing the comparison logic associated with the BEQ instructions. The comparison logic should read the current value on the bus. When executing BEQ, you should compute A−B using the ALU. While this result of the ALU is being driven on the bus, the comparison logic should read the result A−B and output a single “true” or “false” bit for the condition A == B. Your comparison logic should be purely combinational. Feel free to use any CircuitSim components you wish to aid in your implementation. 3.1.5 Register File 3.1.6 Register Select 4 Phase 2 – Implement the Microcontrol Unit In this phase of the project, you will use CircuitSim to implement the microcontrol unit for the LC-3300 processor. This component is referred to as the “Control Logic” in the images and schematics. The microcontroller will contain all of the signal lines to the various parts of the datapath. You must do the following: 1. Read and understand the microcontroller logic: • Please refer to Appendix B: Microcontrol Unit for details. • Note: You will be required to generate the control signals for each state of the processor in the next phase, so make sure you understand the connections between the datapath and the microcontrol unit before moving on. 2. Implement the Microcontrol Unit using CircuitSim. The appendix contains all of the necessary information. Take note that the input and output signals on the schematics directly match the signals marked in the LC-3300 datapath schematic (see Figure 1). 5 Phase 3 – Microcode and Testing In this final stage of the project, you will write the microcode control program that will be loaded into the microcontrol unit you implemented in Phase 2. Then, you will hook up the control unit you built in Phase 2 of the project to the datapath you implemented in Phase 1. Finally, you will test your completed computer using a simple test program and ensure that it properly executes. You must do the following: 1. Open and fill out microcode.xlsx file we’ve provided you (note: the formulas in the provided file will only work with Excel). You will need to mark which control signal is high (that is 1) for each of the states. 2. After you have completed all the microstates, convert the binary strings you just computed into hex and move them into the main ROM. You can just copy and paste the hex column (highlighted yellow) from the spreadsheet directly into the ROM component in Circuitsim. Do the same for the sequencer and condition ROMs. 3. Connect the completed control unit to the datapath you implemented in Phase 1. Using Figures 1 and 2, connect the control signals to their appropriate spots. 4. Finally, it is time to test your completed computer. Use the provided assembler (found in the “assembly” folder) to convert a test program from assembly to hex. For instructions on how to use the assembler and simulator, see README.txt in the “assembly” folder. Note: The simulator does not test your project, it simply provides a model. To test your design, you must load the assembled HEX into CircuitSim. We recommend using test programs that contain a single instruction since you are bound to have a few bugs at this stage of the project. Once you have built confidence, test your processor with the provided pow.s program as a more comprehensive test case. 6 Autograder • Don’t rename the main subcircuit ”Datapath” • Name your PC register as “PC” • Name your IR register as “IR” • Name your state register as “State” • Name your 3 ROMs as ”MAIN”, ”SEQ”, and ”CC” respectively • Reference registers in regfile in lower case with prefixed ‘$’ sign ($zero, $at, $v0…), according to Appendix A: LC-3300 Instruction Set Architecture. • Use only one clock globally, which means you should not use clock components in any subcircuits besides the main datapath. Instead, you should use an input pin and connect the clock signal to that subcircuit in the main datapath. • Use only one RAM as memory • In microcode, use the first row as your first state of FETCH macrostate. • Don’t change the layout of the microcode Excel sheet 7 Deliverables To submit your project, you need to upload the following files to Gradescope: • CircuitSim datapath file (LC-3300.sim) • Microcode file (microcode.xlsx) If you are missing one or both of those files, you will get a 0 so make sure that you have uploaded both of them. Always re-download your assignment from Gradescope after submitting to ensure that all necessary files were properly uploaded. If what we download does not work, you will get a 0 regardless of what is on your machine. This project will be demoed.In order to receive full credit, you must sign up for a demo slot and complete the demo.We will announce when demo times are released. 8 Appendix A: LC-3300 Instruction Set Architecture The LC-3300 is a simple, yet capable computer architecture. The LC-3300 combines attributes of both ARM and the LC-2200 ISA defined in the Ramachandran & Leahy textbook for CS 2200. The LC-3300 is a word-addressable, 32-bit computer. All addresses refer to words, i.e. the first word (four bytes) in memory occupies address 0x0, the second word, 0x1, etc. All memory addresses are truncated to 16 bits on access, discarding the 16 most significant bits if the address was stored in a 32-bit register. This provides roughly 64 KB of addressable memory. 8.1 Registers The LC-3300 has 16 general-purpose registers. While there are no hardware-enforced restraints on the uses of these registers, your code is expected to follow the conventions outlined below. Table 1: Registers and their Uses Register Number Name Use Callee Save? 0 $zero Always Zero NA 1 $at Assembler/Target Address NA 2 $v0 Return Value No 3 $a0 Argument 1 No 4 $a1 Argument 2 No 5 $a2 Argument 3 No 6 $t0 Temporary Variable No 7 $t1 Temporary Variable No 8 $t2 Temporary Variable No 9 $s0 Saved Register Yes 10 $s1 Saved Register Yes 11 $s2 Saved Register Yes 12 $k0 Reserved for OS and Traps NA 13 $sp Stack Pointer No 14 $fp Frame Pointer Yes 15 $ra Return Address No 1. Register 0 is always read as zero. Any values written to it are discarded. Note: for the purposes of this project, you must implement the zero register. Regardless of what is written to this register, it should always output zero. 3. Register 2 is where you should store any returned value from a subroutine call. 4. Registers 3 – 5 are used to store function/subroutine arguments. Note: registers 2 through 8 should be placed on the stack if the caller wants to retain those values. These registers are fair game for the callee (subroutine) to trash. 5. Registers 6 – 8 are designated for temporary variables. The caller must save these registers if they want these values to be retained. 7. Register 12 is reserved for handling interrupts. While it should be implemented, it otherwise will not have any special use on this assignment. 8. Register 13 is the everchanging top of the stack; it keeps track of the top of the activation record for a subroutine. 9. Register 14 is the anchor point of the activation frame. It is used to point to the first address on the activation record for the currently executing process. 10. Register 15 is used to store the address a subroutine should return to when it is finished executing. 8.2 Instruction Overview The LC-3300 supports a variety of instruction forms, only a few of which we will use for this project. The instructions we will implement in this project are summarized below. Table 2: LC-3300 Instruction Set 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0000 DR SR1 unused SR2 0001 DR SR1 unused SR2 0010 DR SR1 immval20 0011 DR BaseR offset20 0100 SR BaseR offset20 0101 SR1 SR2 offset20 0110 AT RA unused 0111 unused 1000 SR1 SR2 offset20 1001 DR unused PCoffset20 1010 DR SR1 unused 00 SR2 1010 DR SR1 unused 01 SR2 1010 DR SR1 unused 10 SR2 1010 DR SR1 unused 11 SR2 1011 SR unused ADD NAND ADDI LW SW BEQ JALR HALT BGT LEA SLL SRL ROL ROR FABS 8.2.1 Conditional Branching Branching in the LC-3300 ISA is a bit different than usual. We have a set of branching instructions including BEQ, BGT, and FABS which offer the ability to branch upon a certain condition being met. These instructions use comparison operators, comparing the values of two source registers. If the comparisons are true (for example, with the BGT instruction, if SR1 > SR2), then we will branch to the target destination of incrementedPC + offset20. For FABS, if SR < 0 then we will branch to the series of microstates for negation. 8.3 Detailed Instruction Reference 8.3.1 ADD Assembler Syntax ADD DR, SR1, SR2 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0000 DR SR1 unused SR2 Operation DR = SR1 + SR2; Description The ADD instruction obtains the first source operand from the SR1 register. The second source operand is obtained from the SR2 register. The second operand is added to the first source operand, and the result is stored in DR. 8.3.2 NAND Assembler Syntax NAND DR, SR1, SR2 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0001 DR SR1 unused SR2 Operation DR = ~(SR1 & SR2); Description The NAND instruction performs a logical NAND (AND NOT) on the source operands obtained from SR1 and SR2. The result is stored in DR. HINT: A logical NOT can be achieved by performing a NAND with both source operands the same. For instance, NAND DR, SR1, SR1…achieves the following logical operation: DR ← SR1. 8.3.3 ADDI Assembler Syntax ADDI DR, SR1, immval20 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0010 DR SR1 immval20 Operation DR = SR1 + SEXT(immval20); Description The ADDI instruction obtains the first source operand from the SR1 register. The second source operand is obtained by sign-extending the immval20 field to 32 bits. The resulting operand is added to the first source operand, and the result is stored in DR. 8.3.4 LW Assembler Syntax LW DR, offset20(BaseR) Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0011 DR BaseR offset20 Operation DR = MEM[BaseR + SEXT(offset20)]; Description An address is computed by sign-extending bits [19:0] to 32 bits and then adding this result to the contents of the register specified by bits [23:20]. The 32-bit word at this address is loaded into DR. 8.3.5 SW Assembler Syntax SW SR, offset20(BaseR) Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0100 SR BaseR offset20 Operation MEM[BaseR + SEXT(offset20)] = SR; Description An address is computed by sign-extending bits [19:0] to 32 bits and then adding this result to the contents of the register specified by bits [23:20]. The 32-bit word obtained from register SR is then stored at this address.8.3.6 BEQ BEQ SR1, SR2, offset20 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0101 SR1 SR2 offset20 Operation if (SR1 == SR2) { PC = incrementedPC + offset20 } Description A branch is taken if SR1 is equal to SR2. If this is the case, the PC will be set to the sum of the incremented PC (since we have already undergone fetch) and the sign-extended offset[19:0]. 8.3.7 JALR Assembler Syntax JALR AT, RA Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0110 AT RA unused Operation RA = PC; PC = AT; Description First, the incremented PC (address of the instruction + 1) is stored into register RA. Next, the PC is loaded with the value of register AT, and the computer resumes execution at the new PC. 8.3.8 HALT Assembler Syntax HALT Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0111 unused Description The machine is brought to a halt and executes no further instructions. 8.3.9 BGT BGT SR1, SR2, offset20 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 1000 SR1 SR2 offset20 Operation if (SR1 > SR2) { PC = incrementedPC + offset20 } Description A branch is taken if SR1 is greater than SR2. If this is the case, the PC will be set to the sum of the incremented PC (since we have already undergone fetch) and the sign-extended offset[19:0]. 8.3.10 LEA Assembler Syntax LEA DR, label Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 1001 DR unused PCoffset20 Operation DR = PC + SEXT(PCoffset20); Description An address is computed by sign-extending bits [19:0] to 32 bits and adding this result to the incremented PC (address of instruction + 1). It then stores the computed address into register DR. 8.3.11 SLL Assembler Syntax SLL DR, SR1, SR2 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 1010 DR SR1 unused 00 SR2 Operation DR = SR1 > SR2; Description The value stored in SR1 is logically right shifted by the value stored in SR2, and the result is stored in DR. 8.3.13 ROL Assembler Syntax ROL DR, SR1, SR2 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 1010 DR SR1 unused 10 SR2 Operation DR = (SR1 > (32 – SR2)); Description Bits in SR1 are ”rotated” left by SR2 number of bits using circular shifting. During a left rotation, the bits that are shifted out from the left are brought back in on the right side. 8.3.14 ROR Assembler Syntax ROR DR, SR1, SR2 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 1010 DR SR1 unused 11 SR2 Operation DR = (SR1 >> SR2) | (SR1
In this homework, you will be implementing an arraylist and debugging code for a “Random Message Generator.” The files we provided include: • main.c: main functions that generate the random message • main.h: header file of the main function • arraylist.c: functions that are used to manipulate the ArrayList (used by main.c) • arraylist.h: header file of ArrayList data structure • arraylisttest.h: header file for the tests for the arraylist data structure. • arraylist test.c: functions for testing the the arraylist data structure • Makefile: A script that can be used for compiling the code (optional). You will be modifying arraylist.c, main.c, and main.h for this homework. Before completing the various parts of this homework, read all the relevant files, and fill in your name and GTID at the top. 2 Part 1: Implement taking in parameters from command lines First, let’s knock out taking in arguments from the command line. There will be two command line arguments for this program. This code should be written in the main method in the main.c file. Look for inline comments that will describe where you should implement your code. The arguments are: • t triggers the program to run the unit tests on the arraylist rather than generating a random message. • l sets the length of the message that the program will generate. We highly recommend using the getopt() function. The method head looks like this: getopt(int argc, char *const argv[], const char *optstring) where argc is the argument count, argv is argument array, and optstring is the specified list of characters, each representing a single character option. If the character in opstring is followed by ’:’, the corresponding option will take in an argument, and that argument will be pointed by optarg. This function will return the next option character (if one is found) from argv that matches a character in optstring. If no character in argv is in optstring or there is a missing argument, it will return ’?.’ If we set the first character of optstring to be ’:’ and we encounter a missing argument situation, it will return ’:’ instead. Otherwise, it will return -1 which indicates that all option characters have been parsed. 2.1 Deliverable 2: GDB Snapshots Your screenshot should include the following: 1. Setting the breakpoint at the appropriate line to print the values stored in variables length and tests 2. Running the program in gdb with appropriate arguments 3. Printing the values of length and tests 4. Delete the breakpoint you set above. 2.2 Compiling and Running In the future, we will provide you with a Makefile for compiling your programs. However, for this assignment, we want you to be aware of how C programs are actually compiled. To compile a program you’ll use the gcc compiler. To use the gcc compiler use the following format: • gcc PATH/TO/C/FILE PATH/TO/C/FILE … -o PROGRAM NAME Or if you’re compiling to debug with gdb: • gcc -g PATH/TO/C/FILE PATH/TO/C/FILE … -o PROGRAM NAME To run the program you will simply need to type the path to your program. One thing to note is that you will have to put “./” before the filename if you are in the same directory as your program. For example, if you use the name Word Generator: • From same directory: ./Word Generator -l 10 • From different directory: ./PATH/…/Word Generator -t 3 Part 2: Implement the ArrayList methods Next, implement the functions for the ArrayList data structure in arraylist.c: • create arraylist: Taking the capacity of the arraylist as an input, create an ArrayList using the backing array with type ** char. Remember to use malloc() to allocate space for the storage of the ArrayList. The function should return a pointer to the ArrayList you created. • add at index: Add a word to ArrayList at a specific index. If the length of the ArrayList is going to exceed the capacity, resize the ArrayList to twice its original capacity. You can call resize(), which is also a function you will implement, to do this. • append: Add a word to the end of the ArrayList. Remember to resize as required in add at index. • remove from index: Remove a word from the ArrayList at a certain index and return the word removed. Make sure to maintain the ArrayList contiguous. • resize: Resize the backing array to hold twice its original capacity. It should now support arraylist->capacity∗ 2 elements. • destroy: Destroy the ArrayList by freeing the ArrayList itself and its backing array. Please refer to the comments in arraylist.h for further guidelines. Also note that arraylist.c is almost blank. In short, you need to implement the functions defined in arraylist.h. Think of arraylist.h as the interface that your code is expected to comply with. If your code passes the arraylist tests sanity tests and your word generator gives the expected output, then your code should be good. We reserve the right to review the code to ensure that your implementation is not hard coded or incorrect (i.e. implemented a link list instead of an array list). 4 Part 3: Debug the main file For the last part of the project, you will need to debug the provided code in main.c and main.h. This code is used to create a “random word generator” that, in short, draws several random words from an array called “Dictionary”. There are 3 problematic lines of code that are causing problems located somewhere throughout the provided code. If you get stuck look for the comments for hints! This section is to prepare you for debugging C code on your projects that are much larger and more complex than this code. The intended output from the program is: • -l 5: Message: this tea Half is nothing • -l 10: Message: this tea is nothing more Half than hot leaf juice • -l 15: Message: this tea is nothing more than hot Half leaf juice cs2200 rocks momo secret tunnel The output shown above should be the only output onto stdout (or stderr) that your program makes when the l argument is used. When the t argument is used only the outputs of the arraylist tests should be shown on stdout (or stderr). We will not run your program with both the t and l arguments used simultaneously. If this part seems tedious, often small bugs that are easily overlooked lead to headaches on the projects. Hopefully, this practice will allow you to locate them easier in the future. 4.1 GDB Debugging Tips If your program is crashing or misbehaving, you can use GDB to locate the bug. GDB is a command line interface that will allow you to set breakpoints, step through your code, see variable values, and identify segfaults. There are tons of online guides, click here (http://condor.depaul.edu/glancast/373class/docs/gdb.html) for one. First (after compiling with the -g flag) load your binary file into GDB using: $ gdb or in our case $ gdb Word Generator Within GDB, you can run your program with the run command: $ (gdb) r Which in our case is either one of these: $ (gdb) r -t $ (gdb) r -l $ (gdb) break main.c:53 ! set breakpoint at call to system init $ (gdb) r -l ! (wait for breakpoint) $ (gdb) s ! step into the function call or by using the actual function name being called from the main loop: $ (gdb) break sim cmd ! set breakpoint at call to sim c $ (gdb) r -l ! (wait for breakpoint) $ (gdb) s ! step into the function call $ (gdb) x/24xb frame table 0x1004000aa: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x1004000b2: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x1004000ba: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 The format of this command is x/nfu [memory location], where n is the number of items to print, f is a formatting identifier, and u is the specifier for the units you would like to print. b specifies 1 byte, h specifies 2 bytes, w specifies 4 bytes, and g specifies 8 bytes. If you use the corruption checker, you can set a breakpoint on panic() and use a backtrace to discover the context in which the panic occurred: $ (gdb) break panic $ (gdb) r -i ! (wait for GDB to stop at the breakpoint) $ (gdb) backtrace $ (gdb) frame N ! where N is the frame number you want to examine Lastly, you can use gdb to see the value of a variable without print statements using: $ (gdb) print 5 Submission Files you will submit on Gradescope: • Your GDB snapshots • arraylist.c • main.c • main.h
Homework 2 – Assembly Review 1 Problem 1: Getting Started with the LC-3300 In this homework, you will be using the LC-3300 ISA to complete a Tower of Hanoi move-counting function. Before you begin, you should familiarize yourself with the available instructions, the register conventions and the calling convention of LC-3300. Details can be found in the section, Appendix A: LC-3300 Instruction Set Architecture, at the end of this document. The assembly folder contains several tools for you to use: • assembler.py: a basic assembler that can take your assembly code and convert it into binary instructions for the LC-3300. • lc3300.py: the ISA definition file for the assembler, which tells assembler.py the instructions supported by the LC-3300 and their formats. • lc3300-sim.py: A simulator of the LC-3300 machine. The simulator reads binary instructions and emulates the LC-3300 machine, letting you single-step through instructions and check their results. To learn how to run these tools, see the README.md file in the assembly directory. Before you begin work on the second problem of the homework, try writing a simple program for the LC-3300 architecture. This should help you familiarize yourself with the available instructions. We have provided a template, mod.s, for you to use for this purpose. Try writing a program that performs the mod operation on the two provided arguments. A correct implementation will result in a value of 2. You can use the following C code snippet as a guide to implement this function: int mod(int a, int b) { int x = a; while (x >= b) { x = x – b; } return x; } There is no turn-in for this portion of the assignment, but it is recommended that you attempt it in order to familiarize yourself with the ISA. 2 Problem 2: Tower of Hanoi For this problem, you will be implementing the missing portions of the program that calculates the minimum number of moves to solve the Tower of Hanoi problem for n disks. You will be finishing a recursive implementation of the Tower of Hanoi minimal moves calculator program that follows the LC-3300 calling convention. Recursive functions always obtain a return address through the function call and return to the callee using the return address. Here is the C code for the Tower of Hanoi minimal moves calculator you have been provided: int minimumHanoi(int n) { if (n == 1) return 1; else return (2 * minimumHanoi(n – 1)) + 1; } Note that this C code is just to help your understanding and does not need to be exactly followed. However, your assembly code implementation should meet all of the given conditions in the description. Open hanoi.s file in the assembly directory. This file contains an implementation of the Tower of Hanoi minimal moves calculator program that is missing significant portions of the calling convention. Near the bottom of the hanoi.s we have provided multiple numbers that you can use to test your homework. They are located at labels testNumDisks1, testNumDisks2, testNumDisks3. Be sure to use these provided integers by loading them from the labels into registers. None of the numbers provided and tested will be lower than 1. Complete the program by implementing the various missing portions of the LC-3300 calling convention. Each location where you need to implement a portion of the calling convention is marked with a TODO label as well as a short hint describing the portion of the calling convention you should be implementing. Try to use logical left shift somewhere in your assembly. 3 Problem 3: Short Answer Please answer the following question in the file named answers.txt: 4 Deliverables • hanoi.s: your assembly code from Section 2 • answers.txt: your answer to the problem from Section 3 5 Appendix A: LC-3300 Instruction Set Architecture The LC-3300 is a simple, yet capable computer architecture. The LC-3300 combines attributes of both ARM and the LC-2200 ISA defined in the Ramachandran & Leahy textbook for CS 2200. The LC-3300 is a word-addressable, 32-bit computer. All addresses refer to words, i.e. the first word (four bytes) in memory occupies address 0x0, the second word, 0x1, etc. All memory addresses are truncated to 16 bits on access, discarding the 16 most significant bits if the address was stored in a 32-bit register. This provides roughly 64 KB of addressable memory. 5.1 Registers The LC-3300 has 16 general-purpose registers. While there are no hardware-enforced restraints on the uses of these registers, your code is expected to follow the conventions outlined below. Table 1: Registers and their Uses Register Number Name Use Callee Save? 0 $zero Always Zero NA 1 $at Assembler/Target Address NA 2 $v0 Return Value No 3 $a0 Argument 1 No 4 $a1 Argument 2 No 5 $a2 Argument 3 No 6 $t0 Temporary Variable No 7 $t1 Temporary Variable No 8 $t2 Temporary Variable No 9 $s0 Saved Register Yes 10 $s1 Saved Register Yes 11 $s2 Saved Register Yes 12 $k0 Reserved for OS and Traps NA 13 $sp Stack Pointer No 14 $fp Frame Pointer Yes 15 $ra Return Address No 1. Register 0 is always read as zero. Any values written to it are discarded. Note: for the purposes of this project, you must implement the zero register. Regardless of what is written to this register, it should always output zero. 3. Register 2 is where you should store any returned value from a subroutine call. 4. Registers 3 – 5 are used to store function/subroutine arguments. Note: registers 2 through 8 should be placed on the stack if the caller wants to retain those values. These registers are fair game for the callee (subroutine) to trash. 5. Registers 6 – 8 are designated for temporary variables. The caller must save these registers if they want these values to be retained. 7. Register 12 is reserved for handling interrupts. While it should be implemented, it otherwise will not have any special use on this assignment. 8. Register 13 is the everchanging top of the stack; it keeps track of the top of the activation record for a subroutine. 9. Register 14 is the anchor point of the activation frame. It is used to point to the first address on the activation record for the currently executing process. 10. Register 15 is used to store the address a subroutine should return to when it is finished executing. 5.2 Instruction Overview The LC-3300 supports a variety of instruction forms, only a few of which we will use for this project. The instructions we will implement in this project are summarized below. Table 2: LC-3300 Instruction Set 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0000 DR SR1 unused SR2 0001 DR SR1 unused SR2 0010 DR SR1 immval20 0011 DR BaseR offset20 0100 SR BaseR offset20 0101 SR1 SR2 offset20 0110 AT RA unused 0111 unused 1000 SR1 SR2 offset20 1001 DR unused PCoffset20 1010 DR SR1 unused 00 SR2 1010 DR SR1 unused 01 SR2 1010 DR SR1 unused 10 SR2 1010 DR SR1 unused 11 SR2 1011 SR unused ADD NAND ADDI LW SW BEQ JALR HALT BGT LEA SLL SRL ROL ROR FABS 5.2.1 Conditional Branching Branching in the LC-3300 ISA is a bit different than usual. We have a set of branching instructions including BEQ, BGT, and FABS which offer the ability to branch upon a certain condition being met. These instructions use comparison operators, comparing the values of two source registers. If the comparisons are true (for example, with the BGT instruction, if SR1 > SR2), then we will branch to the target destination of incrementedPC + offset20. For FABS, if SR < 0 then we will branch to the series of microstates for negation. 5.3 Detailed Instruction Reference 5.3.1 ADD Assembler Syntax ADD DR, SR1, SR2 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0000 DR SR1 unused SR2 Operation DR = SR1 + SR2; Description The ADD instruction obtains the first source operand from the SR1 register. The second source operand is obtained from the SR2 register. The second operand is added to the first source operand, and the result is stored in DR. 5.3.2 NAND Assembler Syntax NAND DR, SR1, SR2 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0001 DR SR1 unused SR2 Operation DR = ~(SR1 & SR2); Description The NAND instruction performs a logical NAND (AND NOT) on the source operands obtained from SR1 and SR2. The result is stored in DR. 5.3.3 ADDI Assembler Syntax ADDI DR, SR1, immval20 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0010 DR SR1 immval20 Operation DR = SR1 + SEXT(immval20); Description The ADDI instruction obtains the first source operand from the SR1 register. The second source operand is obtained by sign-extending the immval20 field to 32 bits. The resulting operand is added to the first source operand, and the result is stored in DR. 5.3.4 LW Assembler Syntax LW DR, offset20(BaseR) Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0011 DR BaseR offset20 Operation DR = MEM[BaseR + SEXT(offset20)]; Description An address is computed by sign-extending bits [19:0] to 32 bits and then adding this result to the contents of the register specified by bits [23:20]. The 32-bit word at this address is loaded into DR.5.3.5 SW SW SR, offset20(BaseR) Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0100 SR BaseR offset20 Operation MEM[BaseR + SEXT(offset20)] = SR; Description An address is computed by sign-extending bits [19:0] to 32 bits and then adding this result to the contents of the register specified by bits [23:20]. The 32-bit word obtained from register SR is then stored at this address. 5.3.6 BEQ Assembler Syntax BEQ SR1, SR2, offset20 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0101 SR1 SR2 offset20 Operation if (SR1 == SR2) { PC = incrementedPC + offset20 } Description A branch is taken if SR1 is equal to SR2. If this is the case, the PC will be set to the sum of the incremented PC (since we have already undergone fetch) and the sign-extended offset[19:0]. 5.3.7 JALR JALR AT, RA Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0110 AT RA unused Operation RA = PC; PC = AT; Description First, the incremented PC (address of the instruction + 1) is stored into register RA. Next, the PC is loaded with the value of register AT, and the computer resumes execution at the new PC. 5.3.8 HALT Assembler Syntax HALT Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 0111 unused Description The machine is brought to a halt and executes no further instructions. 5.3.9 BGT Assembler Syntax BGT SR1, SR2, offset20 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 1000 SR1 SR2 offset20 Operation if (SR1 > SR2) { PC = incrementedPC + offset20 } Description A branch is taken if SR1 is greater than SR2. If this is the case, the PC will be set to the sum of the incremented PC (since we have already undergone fetch) and the sign-extended offset[19:0]. 5.3.10 LEA LEA DR, label Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 1001 DR unused PCoffset20 Operation DR = PC + SEXT(PCoffset20); Description An address is computed by sign-extending bits [19:0] to 32 bits and adding this result to the incremented PC (address of instruction + 1). It then stores the computed address into register DR. 5.3.11 SLL Assembler Syntax SLL DR, SR1, SR2 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 1010 DR SR1 unused 00 SR2 Operation DR = SR1 > SR2; Description The value stored in SR1 is logically right shifted by the value stored in SR2, and the result is stored in DR. 5.3.13 ROL ROL DR, SR1, SR2 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 1010 DR SR1 unused 10 SR2 Operation DR = (SR1 > (32 – SR2)); Description Bits in SR1 are ”rotated” left by SR2 number of bits using circular shifting. During a left rotation, the bits that are shifted out from the left are brought back in on the right side. 5.3.14 ROR Assembler Syntax ROR DR, SR1, SR2 Encoding 31302928272625242322212019181716151413121110 9 8 7 6 5 4 3 2 1 0 1010 DR SR1 unused 11 SR2 Operation DR = (SR1 >> SR2) | (SR1
1 – (14 points) Sanskriti’s pipelined processor features separate instruction and data caches. The instruction cache (I-cache) has a single level and the data cache (D-cache) has three levels, as shown in the following diagram.I-Cache L1 D-Cache L1 D-Cache L2 D-Cache L3 Hit Ratio 97% 88% 75% 72% Access Time 4 cycles 4 cycles 14 cycles 24 cycles Block Size 1 word 1 word 1 word 1 word ● The processor achieves an average CPI of 1.2, without accounting for memory stalls. ● Memory accesses (LWs and SWs) account for 25% of all the instructions executed. ● Out of these memory accesses, 65% are reads and 35% are writes. ● On a cache miss, the CPU experiences a latency of 120 cycles to read from memory, and a latency of 7 cycles to write to memory. ● All caches use the write-through and write-allocate policies. ● There is no write-buffer in the datapath between the CPU and memory bus, hence the CPU must stall until each write reaches memory. For each of the following questions (1.1 to 1.9), show your work to receive credit. Round your final answers to 2 decimal places. For EMAT calculations, give your answer in terms of CPU cycles. Q1.1 (1 points) What percentage of all instructions are loads? What percentage of all instructions are stores? Q1.2 (2 points) Calculate the EMAT for an I-Cache read. Q1.3 (1 point) Calculate the EMAT for a D-cache L3 read. Q1.4 (1 point) Calculate the EMAT for a D-cache L2 read. Q1.5 (2 points) Calculate the EMAT for a D-cache L1 read. Q1.6 (1 point) Calculate the EMAT for a D-cache L3 write. Q1.7 (1 point) Calculate the EMAT for a D-cache L2 write. Q1.8 (2 points) Calculate the EMAT for a D-cache L1 write. Q1.9 (3 points) Calculate the effective CPI of the processor, accounting for all the memory stalls.2 (10 Consider a memory system with 24-bit virtual addresses, 20-bit physical memory addresses, and a page size of 2048 B. Calculate the following for questions 2.1 – 2.4. Q2.1 (2 points) Size of VPN in bits. Q2.2 (2 points) Size of PFN in bits. Q2.3 (1 point) Number of page table entries (answer should be in the format: 2^n). Q2.4 (1 point) Number of frame table entries (answer should be in the format: 2^n). Q2.5 (2 points) A standard page size for virtual memory is 4 KB, but some systems support page sizes of 2 MB or larger. How does the page size affect the frequency of page faults in a virtual memory system? Explain your answer. Q2.6 (2 points) How does the page size affect internal fragmentation? Explain your answer. Question 3 (4 points) Kaylia notices the following virtual page accesses are recorded for three independent processes P1, P2, and P3 respectively over a time interval. P1: 0, 1, 0, 21, 1, 1, 4, 0, 0 P2: 91, 62, 1, 65, 55, 55, 62, 1, 91, 91, 62 P3: 45, 10, 3, 3, 5, 7, 28, 5 What is the cumulative memory pressure on the system during this time interval? 4 (12 Q4.1 (6 points) Consider a direct-mapped cache with 5 sets. Sets are indexed from 0 to 4. The cache block size is a word. Assume that the cache is initially empty and that each memory access operates at word granularity (i.e., all addresses are word addresses). Memory Address Cache Set Accessed Hit or Miss? 0x03 0x04 0x07 0x03 0x02 0x04 a) For the memory accesses shown below starting from an empty cache, fill in the rows. If there is a miss, please specify the type of miss in the table. (3 points total) Memory Address Cache Set Accessed Hit or Miss? 0x01 0x04 0x04 0x05 0x00 0x04 b) For the memory accesses shown below starting from an empty cache, fill in the rows. If there is a miss, please specify the type of miss in the table. (3 points total) Q4.2 (6 points) Now, consider a 3-way set associative cache with 3 sets. The cache uses an LRU replacement policy. Sets are indexed from 0 to 2 and ways are numbered from 0 to 2. The cache block size is a word. Assume that the cache is initially empty and that each memory access operates at word granularity (i.e., all addresses are word addresses). If the cache set is empty, use cache way 0. c) For the memory accesses shown below starting from an empty cache, fill in the rows. If there is a miss, please specify the type of miss in the table. (3 points total) Memory Address Cache Set Accessed Cache Way Accessed Hit or Miss? 0x00 0x03 0x05 0x06 0x09 0x00 d) For the memory accesses shown below starting from an empty cache, fill in the rows. If there is a miss, please specify the type of miss in the table. (3 points total) Memory Address Cache Set Accessed Cache Way Accessed Hit or Miss? 0x04 0x07 0x05 0x07 0x04 0x02(10 Q5.1 (3 points) Nityam decides to design the cache with 256 sets and 16B cache blocks. What are some drawbacks of his design? Q5.2 (3 points) Ayush decides to design the cache with 256 ways and 16B cache blocks. What is another name for Ayush’s cache design? Why might it not perform as well as Nityam’s design? Q5.3 (4 points) Kaylia designs a direct mapped cache, but with 256B cache blocks. What are some of the advantages and disadvantages of this design compared to Nityam’s cache? (11 points) Prasad is an intern at Intel. His job is designing a 4-way set-associative cache with the following characteristics: ● Total cache capacity = 128 KB (1KB = 1024 bytes). ● CPU uses 64-bit byte-addressable memory addresses. ● The cache block size is 64 bytes. ● The cache has one valid bit per cache block. ● The cache uses a write-back policy and uses one dirty bit per 8-byte word to minimize the amount of data that must be written back when an eviction occurs. ● The cache’s replacement policy guarantees that the two most-recently used cache blocks will not be evicted. The MRU fields uniquely identify the two most recently used cache blocks in that cache set. For replacement, one of the remaining 6 ways is chosen at random. However, Prasad never took CS 2200 and is thus completely lost! Help him by answering some questions to design the cache. Q6.1 (2 points) How many sets are in the cache? Q6.2 (3 points) How many bits are needed for the following (1 pt each): a) Block Offset b) Index c) Tag Q6.3 (2 points) How many dirty bits are needed per cache block? Q6.4 (2 points) How many MRU bits are needed per set? Q6.5 (2 points) How many bits are required in total for metadata storage (including MRU)? You don’t need to compute the final sum. (9 points) Consider a paged memory system with 5 physical frames that the OS has reserved strictly for housing application pages. Figure 1 shows a timeline of virtual page accesses with associated timestamps. For example, at timestamp 2, virtual page 10 is accessed. Figure 1: Timeline of Page Accesses Timestamp Virtual Page Accessed 1 1 2 10 3 7 4 3 5 4 6 5 7 1 8 8 9 10 The memory system has a hardware component in the CPU called the Tracker. The Tracker records the access order of all the pages currently in memory. That is, entry 1 holds the most recently accessed page, entry 2 holds the second most recently accessed page, and the last entry holds the least recently accessed page. Figure 2 shows the contents of the Tracker at timestamp 5. Its contents are [4, 3, 7, 10, 1]. The first entry in the Tracker is the most recently accessed page: page 4. The Tracker is accessible to the memory management system in the OS. Figure 2: Contents of the Tracker at timestamp 5 Entry 1 Entry 2 Entry 3 Entry 4 Entry 5 4 3 7 10 1Q7.1 (2 points) Explain how the operating system can use the Tracker component to make page replacement decisions. Q7.2 (2 points) What are the contents of the Tracker at timestamp 9? Q7.3 (3 points) How many total page faults occur in total in this scenario of 9 page accesses. Assume that none of the pages are in physical memory in the beginning. Show your work for credit. Q7.3 (2 points) Would implementing a Tracker component be feasible for a memory system with thousands of physical frames? Explain why or why not.
1 Disk Size Calculation (8 points) Suppose we have a hard disk drive with the following specifications: ● Number of platters: 15 ● Surfaces per platter: 2 ● Tracks per surface: 20000 ● Sectors per track: 400 ● Bytes per sector: 2048 bytes ● Rotational Speed: 4000 RPM ● Average seek time: 20 ms Q1.1 (2 points) How many bytes of data is stored on each platter of the hard disk drive? Leave your answer as a math expression: eg. 2 * 4 * (6 * 9 + 5) Q1.2 (3 points) How much time, in milliseconds, does it take to get to (access) a random sector on the disk? Do NOT include units in your answer. Round to 1 decimal place if needed. Q1.3 (3 points) Now suppose we have a di erent hard disk drive that utilizes zoned bit recording with the following specifications: ● Number of platters: 10 ● Surfaces per platter: 2 ● Bytes per sector: 2048 bytes ● Rotational Speed: 9000 RPM ● Average seek time: 10 ms ● 4 Zones: ○ Zone 0 (Outermost zone): ■ 24 tracks, 48 sectors per track ○ Zone 1: ■ 12 tracks, 30 sectors per track ○ Zone 2: ■ 6 tracks, 20 sectors per track ○ Zone 3: ■ 1 tracks, 6 sectors per track What is the total capacity of this new hard drive in bytes? Leave your answer as a math expression: eg. 2 * 4 * (6 * 9 + 5) 2 Disk Scheduling (12 points) We have a disk with the following specifications: ● Total # of cylinders: 350 (numbered 0 to 349). The outermost cylinder = 0 and the innermost cylinder = 349. ● Current head position = cylinder 190, and the head is currently moving inwards (moving towards cylinder 349) There are 10 pending requests shown below in order of arrival from left to right. Assume that each request transfers an entire track, and, therefore, the disk head can immediately start transferring the track after locating it (i.e., there is no rotational latency incurred to locate a sector). Request ID R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 Cylinder ID 34 50 2 100 49 36 200 250 1 10 Q2.1 (3 points) Write your answer as a comma-separated list of cylinder IDs: eg. 109, 231, 4, 70 Q2.2 (3 points) Write your answer as a comma-separated list of cylinder IDs: eg. 109, 231, 4, 70 Suppose that the latency for moving the head position is M per cylinder, and the latency of transferring a track is C. Give your answers in terms of M and C. Q2.3 (3 points) What is the expected response time for request R10 if the disk scheduling algorithm is SSTF? Answer in terms of M + C: (eg. 49M + 21C) Q2.4 (3 points) What is the expected response time for request R3 if the disk scheduling algorithm is C-LOOK? Answer in terms of M + C: (eg. 49M + 21C) 3 Networking (15 points) Consider the following chunk of a network. All IPs in the figure are IPv4 addresses with a subnet mask of 255.255.255.0.Q3.1 (2 points) How many network layer hops would it take to go from host 139.54.56.99 to host 139.54.25.34? Q3.1 (2 points) How many link layer hops would it take to go from host 139.54.56.99 to host 139.54.25.34? Nityam is responsible for managing a real-time video streaming service that delivers live broadcasts of sports events to viewers worldwide. The service needs to ensure minimal latency and can tolerate some packet loss without significant impact on user experience. Q3.3 (2 points) Which transport layer protocol should Nityam use? Q3.4 (6 points) Explain what characteristic of your chosen protocol makes it preferable for this exchange. Contrast it with the one not chosen in Q3.3. Q3.5 (3 points) If all the following IP addresses have a subnet mask of 20 bits, which ones are in the same subnet as the device with IP 118.211.30.56? Select all that apply. 118.211.31.23 118.211.34.56 118.211.255.18 118.211.16.240 118.212.30.56 120.211.12.56 118.211.1.138 4 Network Routing Algos (9 points) Suppose we have the following network. At each time step starting from t=1, every node sends its distance vector (i.e., a given node’s latency to all the other nodes) to its neighbor. At t=0, all the nodes know the latencies to their respective immediate neighbors.At time t=0, the distance vector for A is as follows: A: 0, B: 2, C: 3, D: x, E: x, F: x Use x to represent an unknown/infinite distance Q4.1 (4 points) Compute the distance vector for A at time t=2. Write your answer as a comma-separated list of distances of all nodes in alphabetical order from A, including A. Example answer for distance vector for A at t=0: 0, 2, 3, x, x, xQ4.2 (5 Compute a link-state routing table at node A for the network after a long period of time has passed. Assume that A already knows the whole topology of the network. Write your answer as a comma-separated list of distances of all nodes in alphabetical order from A, including A. Answer format: , , …, Example answer for link-state routing table at A: 0, 2, 3, 4, 5, 6 5 FAT Disk Allocation (10 points) Assume that we are using a File Allocation Table (FAT) disk allocation scheme that manages 12 data blocks numbered from 1 to 12. The table consists of 4 columns containing metadata for the FAT scheme: 1. Block number (Labeled from 1 to 12) 2. A busy bit 3. The name of the file, or NA if the block is unallocated 4. A block number for the next disk block of that file, or -1 if that block is the corresponding file’s last block. Block Number Busy File Name Next 1 1 Karan -1 2 1 Nami 7 3 1 Fizz 4 4 1 Fizz -1 5 0 NA -1 6 1 Fizz 12 7 1 Nami 8 8 1 Nami -1 9 1 Diana -1 10 0 NA -1 11 1 Diana 9 12 1 Fizz 3 Q5.1 (6 List the data blocks that comprise each file in the correct order. Write your answer as comma-separated list of block numbers for each file: eg. 8, 1, 4, 6 Fizz: Nami: Karan: Diana: Q5.2 (4 points) Explain one advantage and one disadvantage of the File Allocation Table (FAT) scheme. 6 Unix Commands (7 points) Given the following initial directory structure and file contents, write the command you would use to achieve each of the following outcomes.└── a ├── b │ ├── f1 │ ├── f2 │ └── f3 └── c ├── f4 └── f5 . File Name Contents f1 foo f2 bar f3 baz f4 fred f5 waldo Each question below is independent of each other and should each assume restarting from the initial state. ● You are executing your commands from the parent directory “a” ● “b” and “c” are subdirectories of “a” For example, in order to print the contents of f4, you would type cat C/f4(2└── a ├── b │ ├── f1 │ └── f3 └── c ├── f4 └── f5 . File Name Contents f1 foo f3 baz f4 fred f5 waldo What Unix command would you execute to achieve the above changes? Write your answer as a properly formatted Unix command (2└── a ├── b │ ├── f1 │ ├── f2 │ └── f3 └── c ├── f4 ├── f5 └── newfile . File Name Contents f1 foo f2 bar f3 baz f4 fred f5 waldo newfile What Unix command would you execute to achieve the above changes? Write your answer as a properly formatted Unix command (3File Name Contents f1 foo f3 baz f4 fred f5 waldo After executing a command to achieve the above, you run 3 more in succession. The following is the terminal output for doing so: $ $ cat newfile bar $ rm a/b/f2 $ cat newfile error: no such file or directory What was the you executed to achieve the above results? Write your answer as a properly formatted Unix commandQuestion 7 – Network Transmission (9 points) Suppose now that you are trying to send a 30,000 byte file to your friend, and you’d like to take advantage of TCP for the transmission. Suppose also that ● The size of each TCP packet is 2000 bytes ● The size of a TCP packet header is 500 bytes ● We have a fixed window size of 5 packets ● Time of flight is 11 ms ● Assume negligible overhead at sender and receiver. ● Wire bandwidth is 18 Mbps ● Assume for simplicity that an ACK has negligible transmission delay Q7.1 (2 point) What is the total number of packets you will need to send to your friend? Q7.2 (1 point) How many pipelined transmission windows will you need to send over all the packets? Q7.3 (4 points) Compute the end-to-end transmission time, in milliseconds, to send 1 window of packets. Assume the window contains packets with full payloads. Do NOT include units in your answer. Round to 1 decimal place if needed. Q7.4 (2 points) Still using sliding window transmission, compute the end-to-end transmission time, in milliseconds, to send all packets. Assume the window contains packets with full payloads. Do NOT include units in your answer. Round to 1 decimal place if needed. Appendix Unix Command Semantics touch Create an empty file with name mkdir Create a sub-directory rm Remove or delete the file named rmdir Remove or delete the sub-directory named ln -s Create a name and make it symbolically equivalent to the file ln Create a name and make it physically equivalent to the file chmod Change the access rights for the file as specified in the mask chown Change the owner of the file to be chgrp Change the group associated with the file to be cp Create a new file that is a copy of the file mv Renames the file with the name cat/more/less View the file contents p_thread library function
Question 1 (8 points) Consider the following five stage pipeline for the LC-2200 ISA.List the minimum buffer contents needed to execute the following two instructions in our LC-2200 pipeline ISA. Refer to the Appendix for instruction formats. Interrupts must be supported. (1 pt for each buffer). Please ensure that your answer matches the following notations. – Notation to denote a 32 bit instruction: Instruction – Notation to denote Opcode: Opcode – Notation to denote register specifiers: Rx, Ry, Rz – Notation to denote contents of registers: [Rx], [Ry], [Rz] – Notation to denote sign-extended offset: Offset – Notation to denote ALU output: ALU-result – Notation to denote PC: PC Q1.1 (4 points) List the minimum buffer contents needed to execute the SW Instruction.Q1.2 (4 points) List the minimum buffer contents needed to execute the CAP Instruction. The CAP instruction performs the logical NOT of the number in the source register Ry and stores the result in destination register Rx. Hint: Logical NAND of a number by itself is equivalent to the logical NOT of the number.Question 2 (10 points) Q2.1 (8 points) Consider the following snippet of LC-2200 assembly code. List the different types of data dependencies (RAW, WAR, WAW) that exist between every pair of instructions in the following listing. If there is no applicable data hazard, enter “N/A.” i1: ADDI $s0, $s1, 20 i2: LW $t0, 3($s0) i3: SW $t0, 1($t1) i4: NAND $s1, $t0, $s2 Example answer format: RAW: i5-i6, i10-i12 WAR: N/A WAW: i7-i8 Q2.2 (2 points) Given the following instruction i1, write an instruction i2 that directly follows i1 and has both a WAR and a RAW data dependency with i1. i1: ADD $s0, $t1, $t2 Question 3 (18 points) Q3.1 (8 points) Consider the following snippet of assembly code. Assume that the initial values for registers $t0 and $t1 are $t0 = 3 and $t1 = 6. Note that the code uses the BNE instruction (branch if not equal to). You can assume that ADDI works the same as it does in the LC-2200 ISA. 1 loop: 2 addi $t0, $t0, -1 ! Decrement $t0 ($t0 = $t0 – 1) 3 addi $t1, $t1, -1 ! Increment $t1 ($t1 = $t1 + 1) 4 addi $v0, $v0, 1 ! Increment $v0 by 1 5 bne $t0, $t1, loop ! Branch to end if $t0 not equal to $t1 (Not taken) 6 bne $t0, $zero, loop ! Branch to loop if $t0 not equal to 0 7 addi $t1, $zero, 15 ! $t1 = $zero + 15 Assume these instructions are executed on the LC-2200’s five-stage pipeline, but with register forwarding available from all stages following the ID/RR stage. The pipeline is not equipped with any form of branch prediction, and the ISA does not support branch delay slots. Q3.2 (10 points) Consider the following snippet of assembly code. 1 add $v0, $zero, $zero ! Initialize $v0 to 0, $v0 =$zero + $zero 2 addi $t0, $zero, 2 ! Initialize $t0 to 2, $t0 = $zero +2 3 addi $t0, $t0, -1 ! Decrement $t0, $t0 = $t0 – 1 4 addi $v0, $t1, 1 ! Perform: $v0 = $t1 + 1 5 addi $t1, $zero, 15 ! Perform: $t1 = $zero + 15 Assume the following snippet is executed using the following pipeline:The above 9-stage pipeline has data forwarding only from the “MEM” and “Execute” stages to the “Register File read” stage. Reference this pipeline structure for the following two questions. Assume that arithmetic for ADD/ADDI instruction happens in the “Execute” stage of the pipeline. Q3.2.a (6 points) Considering the above code snippet and the 9-stage pipeline, list EACH pair of instructions that will result in a data hazard; and for each such pair state the number of pipeline bubbles that will occur. For each hazard type, example format: (I1,I2):2,(I1,I3):1 for 2 bubbles between I1 and I2 and 1 bubble between I1 and I3.. If there is no applicable data hazard, enter “N/A.” If applicable, clearly state any assumptions for this question in the assumptions box at the end of the exam. a) List all the RAW hazard pairs and bubbles. b) List all the WAR hazard pairs and bubbles. c) List all the WAW hazard pairs and bubbles. Q3.2.b (4 points) Could you improve the pipeline’s performance for the given set of instructions, by only adding extra forwarding paths in the pipeline? Please explain. Question 4 (11 points) Consider the following three processes P1, P2, and P3: P1 P2 P3 CPU Burst Time 4 2 1 I/O Burst Time 2 1 2 Assume each process first completes a CPU burst, followed by I/O burst, and then another CPU burst (of the same length as the first CPU burst) before terminating. Assume no preemption for both parts. Q4.1 (3 points) Assume that the scheduler uses the First-Come, First-Served (FCFS) scheduling algorithm. You can assume that all processes arrive at time 0, but the scheduler decides the arrival order to be P1, followed by P2, followed by P3. (0.5 points for each question answered correctly). a) At what time does P1 start its first CPU burst? b) At what time does P1 finish? c) At what time does P2 start its first CPU burst? d) At what time does P2 finish? e) At what time does P3 start its first CPU burst? f) At what time does P3 finish? Q4.2 (3 points) Assume that the scheduler now uses the Shortest Job First (SJF) scheduling algorithm. You can assume that all processes arrive at time 0. (0.5 points for each question answered correctly). a) At what time does P1 start its first CPU burst? b) At what time does P1 finish? c) At what time does P2 start its first CPU burst? d) At what time does P2 finish? e) At what time does P3 start its first CPU burst? f) At what time does P3 finish? Q4.3 (2 points) When the scheduler uses the FCFS scheduling algorithm, what is the average turnaround time? Please show work. Q4.4 (3 points) When the scheduler uses the FCFS scheduling algorithm, what is the waiting time for each process? Please show work. Question 5 (13 points) Harper is implementing a round robin scheduler. Each process gets a full time quantum on the processor when it is scheduled. If a process gives up the CPU to do I/O before its time quantum is finished, then the time quantum is reset for the next scheduled process. The ready queue contains four processes: P1, P2, P3, P4 (which arrive in that order). The execution characteristics of the four processes are as shown below. Each process begins with a CPU burst, followed by an I/O burst, and then one final CPU burst before finishing. The length of each burst is also given in time units (note that the diagrams are not to scale). P1 (arrives first) CPU Burst (9 time units) I/O Burst (2) CPU Burst (2) P2 (arrives following P1) CPU Burst (2) I/O Burst (2) CPU Burst (2) P3 (arrives following P2) CPU Burst (2) I/O Burst (1) CPU Burst (2) P4 (arrives following P3) CPU Burst (2) I/O Burst (1) CPU Burst (1) Harper is deciding between different timeslices for his round robin scheduler. Assume 0 time for context switching, scheduling, and dispatching. Q5.1 (4 points) a) At what time does P1 start its first CPU burst? b) At what time does P1 completely finish? c) At what time does P2 start its first CPU burst? d) At what time does P2 completely finish? e) At what time does P3 start its first CPU burst? f) At what time does P3 completely finish? g) At what time does P4 start its first CPU burst? h) At what time does P4 completely finish? Q5.2 (1 point) Help Harper by calculating the average waiting time for the above processes when the scheduler’s timeslice is 5 time units instead. Show your work for credit, and leave your final answer as a fraction. Q5.3 (4 points) What is an advantage of longer timeslices? Why? Q5.4 (4 points) What is an advantage of shorter timeslices? Why? Question 6 (10 points) Consider the following tables. Table A demonstrates a variable size partition scheme. Table B demonstrates a fixed size partition scheme. Assume that P1 has a memory footprint of 4K, P2 has a footprint of 6K, and P3 has a footprint of 12K. Memory Footprints of each process Process Memory Footprint P1 4K P2 6K P3 12K Variable size partitions Index Owning Process Memory 1 P1 4K 2 Unallocated 11K 3 P3 12K 4 Unallocated 5K 5 P2 6K Fixed size partitions Index Owning Process Memory 1 P1 8K 2 Unallocated 5K 3 P3 5K 4 P3 10K 5 Unallocated 2K 6 P2 8K Q6.1 (2 points) A new process (P4) is about to be run with a memory footprint of 1K. For each of the two partitioning schemes, indicate in which partition process 4 will be placed. Where it is relevant, use a best fit policy, which allocates the smallest free partition that meets the requirement of the requesting process. a) What index would P4 be allocated to in the variable size partitioning scheme? b) What index would P4 be allocated to in the fixed size partitioning scheme? Q6.2 (4 points) Assume that shortly after P4 starts, P3 ends its execution and exits. Also assume that you had placed P4 in index 2 for both schemes. Please show work for all parts. a) What is the total internal fragmentation for the variable size partitioning scheme? b) What is the total internal fragmentation for the fixed size partitioning scheme? c) What is the total external fragmentation for the variable size partitioning scheme? d) What is the total external fragmentation for the fixed size partitioning scheme? Q6.3 (4 points) List an advantage for variable partitioning schemes. List an advantage for fixed size partitioning schemes. Appendix:LC 2200 ISA with an additional LEA and BGT instruction Mnemonic Example Opcode (Binary) Action Register Transfer Language add add $v0, $a0, $a1 0000 Add contents of reg Y with contents of reg Z, store results in reg X. RTL: $v0 ← $a0 + $a1 nand nand $v0, $a0, $a1 0001 Nand contents of reg Y with contents of reg Z, store results in reg X. RTL: $v0 ← ~($a0 && $a1) addi addi $v0, $a0, 25 0010 Add Immediate value to the contents of reg Y and store the result in reg X. RTL: $v0←$a0+25 lw 0011 Load reg X from memory. The memory address islw $v0, 0x42($fp) formed by adding OFFSET to the contents of reg Y. RTL: $v0 ← MEM[$fp + 0x42] sw sw $a0, 0x42($fp) 0100 Store reg X into memory. The memory address is formed by adding OFFSET to the contents of reg Y. RTL: MEM[$fp + 0x42] ← $a0 beq beq $a0, $a1, done 0101 Compare the contents of reg X and reg Y. If they are the same, then branch to the address PC+1+OFFSET, where PC is the address of the beq instruction. RTL: if($a0 == $a1) PC ← PC+1+OFFSET jalr jalr $at, $ra 0110 First store PC+1 into reg Y, where PC is the address of the jalr instruction. Then branch to the address now contained in reg X. Note that if reg X is the same as reg Y, the processor will first store PC+1 into that register, then end up branching to PC+1. RTL: $ra ← PC+1; PC ← $at Note that an unconditional jump can be realized using jalr $ra, $t0, and discarding the value stored in $t0 by the instruction. This is why there is no separate jump instruction in LC-2200.halt 0111 Halt the machine bgt bgt $a0, $a1, done 1000 Compare the contents of reg X and reg Y. If the value in reg X is greater than the value in reg Y, then branch to the address PC+1+OFFSET, where PC is the address of the bgt instruction. RTL: if($a0 > $a1) PC ← PC+1+OFFSET lea lea $a0, stack 1001 An address is computed by sign-extending bits [19:0] to 32 bits and adding this result to the incremented PC (address of instruction + 1). It then stores the computed address into register DR. RTL: $a0 = MEM[stack]
Question 1 (10 points): High-level languages provide a “switch” statement that looks as follows. switch(k) { case 0: case 1: case 2: … case N: default: } The compiler writer Kaylia knows that “k” can take non-negative contiguous integer values from 0 to N during execution, with any value greater than N going to the default case. She decides to use a jump table data structure (implemented as an array indexed by the value contained in k) to hold the start address for the code for each of the case values as shown below:Assume we are using the modified LC-2200 instruction set architecture, which can be found in the appendix. Q1.1 (4 points) Assume the base address of the jump table is stored in the register $t0, the value of N is stored in register $a0, and the value of k is stored in the register $t1. Help Kaylia out by writing a series of LC-2200 instructions for any positive value of k. Q1.2 (6 points) Instead of using a jump table, her friend suggests using a series of conditional branch instructions to compile the switch statement. List one reason why conditional branches could be better, and one reason why switch statements could be better. Explain your answer, clearly stating your assumptions. Question 2 (12 points): You are given 23 clock cycles of control signals which is a subsection of the execution macro states of some assembly code. Fill out the 4 lines of LC-2200 assembly instructions that correspond to the control signals. Note that the clock cycles corresponding to the fetch macrostate have been omitted. ________________ ________________ ________________ ________________ .fill Label_X 0x1111 Cycle 4: DrREG, LdA, RegSel = $t0 Cycle 5: DrREG, LdB, RegSel = $t0 Cycle 6: ALU=add, DrALU, WrREG, RegSel=$t1Cycle 10: DrREG, LdA, RegSel = $t1 Cycle 11: DrREG, LdA, RegSel = $t1 Cycle 12: ALU=add, DrALU, WrReg, RegSel=$t1Cycle 16: DrREG, LdA, RegSel = $t1 Cycle 17: DrOFF, LdB [Offset = 1] Cycle 18: ALU=add, DrALU, WrREG, RegSel = $t2Cycle 22: DrPC, WrREG, RegSel=$at Cycle 23: DrREG, LdPC Question 4 (8 points): Consider an architecture that has 3 interrupt priority levels. The interrupt handler for every device enables interrupts before executing the device-specific code. The below diagram shows four devices. Smaller numbers represent a higher priority level. B is electrically closer to the processor than D. The INTA line is chained through devices B and D.Time Interrupted By INTA 0 C 100 D 200 INTA 300 B 400 A 500 INTA 600 INTA … 900 INTA Q4.1 (4 points) In what order are the three devices acknowledged? Explain your answer. Q4.2 (4 points) Assuming that these are the only interrupts, in what order do the interrupt handlers complete? Explain your answer. Question 5 (10 points): Kaylia has a program that consists of the following 3 lines, but repeats 220 times. add $t0, $t0, $t0 sw $t0, 0($sp) addi $sp, $sp, -1 In this implementation, the add instruction takes 4 clock cycles. The sw instruction takes 5 clock cycles. The addi instruction takes 3 clock cycles. Each clock cycle takes 7 nanoseconds. Q5.1 (2 points) What is the execution time of this program? Q5.2 (2 points) If Kaylia changes her implementation so the sw instruction now takes 3 clock cycles, what is the new execution time? Round to the nearest nanosecond. Q5.3 (3 points) What is the speedup achieved after this change? Leave your answer as a fraction. Q5.4 (3 points) What is the improvement in execution time after this change? Leave your answer as a fraction. Question 6 (10 points): Consider the following program that contains 600 instructions: I1: I2: I3: … I330: I331: LEA I332: … I343: I344: COND BR to I330 I345: I346: …….. I599: HALT I600: LEA LEA instruction occurs exactly twice in the program as shown. Instructions 330-344 constitute a loop that gets executed 150 times. All other instructions execute exactly once. Leave your answer as a fraction. Q6.1 (5 points) What is the static frequency of LEA instruction? Show your work for credit. Q6.2 (5 points) What is the dynamic frequency of LEA instruction? Show your work for credit. Question 7 (10 points): For the struct defined below, show how a smart compiler might pack the data to minimize wasted space and follow alignment restrictions. Pack in such a way that each member is naturally aligned based on its data type. Assume the compiler will not reorder fields of the struct in memory. Assume a char is 1 byte, an int is 4 bytes, and a short is 2 bytes, and an int64_t is 8 bytes. Moreover, assume the CPU architecture is big-endian and its granularity supports load word (LW), load byte (LB), and load half-word (LHW), where a memory word is 4 bytes. struct x { int a; int64_t b; char d; short e[1]; } data = { 0xBEEF2D6F, 0x021420241324B9CF, 0x24, {0x0C67} }; Q7.1 (10 points) Assume struct data is saved at 0x1000. Fill out this table with the hex values of the data stored at each memory address +0 +1 +2 +3 Starting Address 0x1000 0x1004 0x1008 0x100C 0x1010 Q7.2 (2 points) CPU issues the following instruction: LW R1, MEM[0x1008]. Show the content of R1. Q7.3 (1 point) You are a clever programmer who knows the architectural details and how the compiler will pack the variables to optimize on space. Reorder the elements of struct data such that it will result in optimal space usage. Q7.4 (1 point) How many bytes do you save by reordering the elements of struct data? Question 8 (10 points): Consider the datapath with the delays shown below. Solid lines are data lines; dashed lines are control lines. All times are given in picoseconds – e.g., reading from or writing to the register file takes 2 picoseconds (2×10^-12s). What is the minimum clock cycle in ps?Component Delay (ps) Notes Wire 2 ALU 3 Combinational Register hold + setup 4 For IR,PC,A,B Register output-stable 2 For IR,PC,A,B Memory 200 Level Logic SPRF Access (read or write) 3 MUX 2Appendix: LC 2200 ISA with an additional LEA and BGT instruction Mnemonic Example Opcode (Binary) Action Register Transfer Language add add $v0, $a0, $a1 0000 Add contents of reg Y with contents of reg Z, store results in reg X. RTL: $v0 ← $a0 + $a1 nand nand $v0, $a0, $a1 0001 Nand contents of reg Y with contents of reg Z, store results in reg X. RTL: $v0 ← ~($a0 && $a1) addi addi $v0, $a0, 25 0010 Add Immediate value to the contents of reg Y and store the result in reg X. RTL: $v0←$a0+25 lw lw $v0, 0x42($fp) 0011 Load reg X from memory. The memory address is formed by adding OFFSET to the contents of reg Y. RTL: $v0 ← MEM[$fp + 0x42] sw sw $a0, 0x42($fp) 0100 Store reg X into memory. The memory address is formed by adding OFFSET to the contents of reg Y. RTL: MEM[$fp + 0x42] ← $a0 beq beq $a0, $a1, done 0101 Compare the contents of reg X and reg Y. If they are the same, then branch to the address PC+1+OFFSET, where PC is the address of the beq instruction. RTL: if($a0 == $a1) PC ← PC+1+OFFSET jalr jalr $at, $ra 0110 First store PC+1 into reg Y, where PC is the address of the jalr instruction. Then branch to the address now contained in reg X. Note that if reg X is the same as reg Y, the processor will first store PC+1 into that register, then end up branching to PC+1. RTL: $ra ← PC+1; PC ← $at Note that an unconditional jump can be realized using jalr $ra, $t0, and discarding the value stored in $t0 by the instruction. This is why there is no separate jump instruction in LC-2200. halt 0111 Halt the machinebgt bgt $a0, $a1, done 1000 Compare the contents of reg X and reg Y. If the value in reg X is greater than the value in reg Y, then branch to the address PC+1+OFFSET, where PC is the address of the bgt instruction. RTL: if($a0 > $a1) PC ← PC+1+OFFSET lea lea $a0, stack 1001 An address is computed by sign-extending bits [19:0] to 32 bits and adding this result to the incremented PC (address of instruction + 1). It then stores the computed address into register DR. RTL: $a0 = MEM[stack]
1 – (14 points) Sanskriti’s pipelined processor features separate instruction and data caches. The instruction cache (I-cache) has a single level and the data cache (D-cache) has three levels, as shown in the following diagram.I-Cache L1 D-Cache L1 D-Cache L2 D-Cache L3 Hit Ratio 97% 88% 75% 72% Access Time 4 cycles 4 cycles 14 cycles 24 cycles Block Size 1 word 1 word 1 word 1 word ● The processor achieves an average CPI of 1.2, without accounting for memory stalls. ● Memory accesses (LWs and SWs) account for 25% of all the instructions executed. ● Out of these memory accesses, 65% are reads and 35% are writes. ● On a cache miss, the CPU experiences a latency of 120 cycles to read from memory, and a latency of 7 cycles to write to memory. ● All caches use the write-through and write-allocate policies. ● There is no write-buffer in the datapath between the CPU and memory bus, hence the CPU must stall until each write reaches memory. For each of the following questions (1.1 to 1.9), show your work to receive credit. Round your final answers to 2 decimal places. For EMAT calculations, give your answer in terms of CPU cycles. Q1.1 (1 points) What percentage of all instructions are loads? What percentage of all instructions are stores? Q1.2 (2 points) Calculate the EMAT for an I-Cache read. Q1.3 (1 point) Calculate the EMAT for a D-cache L3 read. Q1.4 (1 point) Calculate the EMAT for a D-cache L2 read. Q1.5 (2 points) Calculate the EMAT for a D-cache L1 read. Q1.6 (1 point) Calculate the EMAT for a D-cache L3 write. Q1.7 (1 point) Calculate the EMAT for a D-cache L2 write. Q1.8 (2 points) Calculate the EMAT for a D-cache L1 write. Q1.9 (3 points) Calculate the effective CPI of the processor, accounting for all the memory stalls.2 (10 Consider a memory system with 24-bit virtual addresses, 20-bit physical memory addresses, and a page size of 2048 B. Calculate the following for questions 2.1 – 2.4. Q2.1 (2 points) Size of VPN in bits. Q2.2 (2 points) Size of PFN in bits. Q2.3 (1 point) Number of page table entries (answer should be in the format: 2^n). Q2.4 (1 point) Number of frame table entries (answer should be in the format: 2^n). Q2.5 (2 points) A standard page size for virtual memory is 4 KB, but some systems support page sizes of 2 MB or larger. How does the page size affect the frequency of page faults in a virtual memory system? Explain your answer. Q2.6 (2 points) How does the page size affect internal fragmentation? Explain your answer. Question 3 (4 points) Kaylia notices the following virtual page accesses are recorded for three independent processes P1, P2, and P3 respectively over a time interval. P1: 0, 1, 0, 21, 1, 1, 4, 0, 0 P2: 91, 62, 1, 65, 55, 55, 62, 1, 91, 91, 62 P3: 45, 10, 3, 3, 5, 7, 28, 5 What is the cumulative memory pressure on the system during this time interval? 4 (12 Q4.1 (6 points) Consider a direct-mapped cache with 5 sets. Sets are indexed from 0 to 4. The cache block size is a word. Assume that the cache is initially empty and that each memory access operates at word granularity (i.e., all addresses are word addresses). Memory Address Cache Set Accessed Hit or Miss? 0x03 0x04 0x07 0x03 0x02 0x04 a) For the memory accesses shown below starting from an empty cache, fill in the rows. If there is a miss, please specify the type of miss in the table. (3 points total) Memory Address Cache Set Accessed Hit or Miss? 0x01 0x04 0x04 0x05 0x00 0x04 b) For the memory accesses shown below starting from an empty cache, fill in the rows. If there is a miss, please specify the type of miss in the table. (3 points total) Q4.2 (6 points) Now, consider a 3-way set associative cache with 3 sets. The cache uses an LRU replacement policy. Sets are indexed from 0 to 2 and ways are numbered from 0 to 2. The cache block size is a word. Assume that the cache is initially empty and that each memory access operates at word granularity (i.e., all addresses are word addresses). If the cache set is empty, use cache way 0. c) For the memory accesses shown below starting from an empty cache, fill in the rows. If there is a miss, please specify the type of miss in the table. (3 points total) Memory Address Cache Set Accessed Cache Way Accessed Hit or Miss? 0x00 0x03 0x05 0x06 0x09 0x00 d) For the memory accesses shown below starting from an empty cache, fill in the rows. If there is a miss, please specify the type of miss in the table. (3 points total) Memory Address Cache Set Accessed Cache Way Accessed Hit or Miss? 0x04 0x07 0x05 0x07 0x04 0x02(10 Q5.1 (3 points) Nityam decides to design the cache with 256 sets and 16B cache blocks. What are some drawbacks of his design? Q5.2 (3 points) Ayush decides to design the cache with 256 ways and 16B cache blocks. What is another name for Ayush’s cache design? Why might it not perform as well as Nityam’s design? Q5.3 (4 points) Kaylia designs a direct mapped cache, but with 256B cache blocks. What are some of the advantages and disadvantages of this design compared to Nityam’s cache? (11 points) Prasad is an intern at Intel. His job is designing a 4-way set-associative cache with the following characteristics: ● Total cache capacity = 128 KB (1KB = 1024 bytes). ● CPU uses 64-bit byte-addressable memory addresses. ● The cache block size is 64 bytes. ● The cache has one valid bit per cache block. ● The cache uses a write-back policy and uses one dirty bit per 8-byte word to minimize the amount of data that must be written back when an eviction occurs. ● The cache’s replacement policy guarantees that the two most-recently used cache blocks will not be evicted. The MRU fields uniquely identify the two most recently used cache blocks in that cache set. For replacement, one of the remaining 6 ways is chosen at random. However, Prasad never took CS 2200 and is thus completely lost! Help him by answering some questions to design the cache. Q6.1 (2 points) How many sets are in the cache? Q6.2 (3 points) How many bits are needed for the following (1 pt each): a) Block Offset b) Index c) Tag Q6.3 (2 points) How many dirty bits are needed per cache block? Q6.4 (2 points) How many MRU bits are needed per set? Q6.5 (2 points) How many bits are required in total for metadata storage (including MRU)? You don’t need to compute the final sum. (9 points) Consider a paged memory system with 5 physical frames that the OS has reserved strictly for housing application pages. Figure 1 shows a timeline of virtual page accesses with associated timestamps. For example, at timestamp 2, virtual page 10 is accessed. Figure 1: Timeline of Page Accesses Timestamp Virtual Page Accessed 1 1 2 10 3 7 4 3 5 4 6 5 7 1 8 8 9 10 The memory system has a hardware component in the CPU called the Tracker. The Tracker records the access order of all the pages currently in memory. That is, entry 1 holds the most recently accessed page, entry 2 holds the second most recently accessed page, and the last entry holds the least recently accessed page. Figure 2 shows the contents of the Tracker at timestamp 5. Its contents are [4, 3, 7, 10, 1]. The first entry in the Tracker is the most recently accessed page: page 4. The Tracker is accessible to the memory management system in the OS. Figure 2: Contents of the Tracker at timestamp 5 Entry 1 Entry 2 Entry 3 Entry 4 Entry 5 4 3 7 10 1Q7.1 (2 points) Explain how the operating system can use the Tracker component to make page replacement decisions. Q7.2 (2 points) What are the contents of the Tracker at timestamp 9? Q7.3 (3 points) How many total page faults occur in total in this scenario of 9 page accesses. Assume that none of the pages are in physical memory in the beginning. Show your work for credit. Q7.3 (2 points) Would implementing a Tracker component be feasible for a memory system with thousands of physical frames? Explain why or why not.
1 General 1.1 Introduction Hello and welcome to Project 3. In this project, you’ll be implementing a word processor. The project has been divided into multiple subroutines that you need to implement. 1.2 General Instructions • Take a look at Section 6 for details on the LC-3 Assembly Programming requirements that you must adhere to. 1.3 Running the autograder Take a look at section 5 for information on how to run the autograder, and how to debug your code. For this project, we will be using LC3Tools, which can be downloaded from Canvas files. 2 Absolute Sum of Array We’ll start with a warm up program before we get to the main chunk of the project. Here you will implement a program that calculates the sum of the absolute values of each element of the array. Memory at the label ARR contains the address of the first element of the array and LEN contains the number of elements present in that array. You should store the resulting sum in the address that the label ANSWER specifies. Example: array = { 1, 3, -4, -2} sum = 1 + 3 + 4 + 2 = 10 Please write your code is asoluteSum.asm. Please do not modify the .orig address as it will cause issues in the autograder. Suggested Pseudocode:answer = 0; currNum = 0; i = 0; arrLength = arr.length(); while (arrLength > 0) { currNum = arr[i]; if (currNum < 0) { currNum = -(currNum); } answer += currNum; i++; arrLength–; } return 3 Word Processor We’re getting into the real meat of the project now. You will be implementing a word processor that takes in an input paragraph, and your job is to divide into lines of 8 characters and perform some modifying to each line. Detailed explanations on what you have to do are explained later. Also, we have divided this segment into smaller subroutines to make it easier. We strongly recommend that you do them in order. 3.1 wordLength To start off, you will implement a function that calculates the length of a word until space, newline, or null char. The starting address of the word will be present in register R0 when this subroutine is called. Special characters and numbers should be treated as regular letters and should be added to the length. Store the resulting word length back into R0. Example: “Hello” : wordLength = 5 “this,” : wordLength = 5 Please do not modify the .orig address as it will cause issues in the autograder. Suggested Pseudocode:def wordLength(R0): addr = R0 length = 0 while (true): if (mem[addr] == ’’): break if (mem[addr] == ’ ’): break if (mem[addr] == ’ ’): break addr += 1 length += 1 R0 = length return 3.2 memcpy This subroutine uses 3 parameters: starting address, destination address, and length (n). This function should copy a total of n characters starting from the starting address into the address specified by destination address. Starting address will be present in register R0 Destination address will be present in register R1 Length (n) will be present in register R2 Please do not modify the .orig address as it will cause issues in the autograder. Suggested Pseudocode:def memcpy(R0, R1, R2): sourcePtr = R0 destPtr = R1 length = R2 while (length > 0): mem[destPtr] = mem[sourcePtr] sourcePtr += 1 destPtr += 1 length -= 1 return 3.3 capitalizeLine This subroutine takes in a starting address of a line in memory and should capitalize all characters in-place until a newline ( ) or null character is encountered (). The starting address will be present in register R0. Example: If the starting address is x4000, the before and after this subroutine is called is shown below:Note: Capital letters and special characters should NOT be modified. Please do not modify the .orig address as it will cause issues in the autograder. Suggested Pseudocode:def capitalizeLine(R0): addr = R0 while (mem[addr] != ’’ and mem[addr] != ’ ’): if (mem[addr] >= ’a’ and mem[addr] 0): mem[i] = stack.pop() i++ count-return 3.5 rightJustify Just like the other subroutines, this one also takes in the starting address of a line and modifies the line inplace. For each space on the right-hand side of the line (before newline or null character), shift all characters in the line to the right by 1, and add a space on the left. Do this until there are no more spaces on the RHS. The starting address of the line will be present in R0. Example: “Low-level coding, high-level fun! ” Should become “ Low-level coding, high-level fun! ”Please do not modify the .orig address as it will cause issues in the autograder. Suggested Pseudocode:def rightJustify(R0): start = R0 curr = start while (mem[curr] != ’ ’ and mem[curr] != ’’): curr++ curr-end = curr // This loop shifts over the entire string one spacebar at a time, // until it is no longer terminated by a spacebar! while (mem[end] == ’ ’): while (curr != start): mem[curr] = mem[curr – 1] curr-mem[curr] = ’ ’ curr = end return 3.6 getInput Please do not modify the .orig address as it will cause issues in the autograder. Suggested Pseudocode:def getInput(R0): bufferPointer = R0 while (true): input = GETC() OUT(input) mem[bufferPointer] = input if input == ’$’: if mem[bufferPointer – 1] == ’$’: mem[bufferPointer – 1] = ’’ break bufferPointer += 1 3.7 parseLines This function should parse a string of characters from an initial buffer and place the parsed string in a new buffer. This method should divide the string into lines of 8 characters or less, not including the NewLine character! If a word cannot fit within the current line, add space bars to pad the current line so it is 8 characters long, and place the word on the next line. The address of the buffer containing the unparsed string will be passed in R0, and the address of the destination buffer will be passed through R1. Please do not modify the .orig address as it will cause issues in the autograder. For the purpose of this this project, this subroutine assumes that ALL words inputted will have a maximum of 8 characters This subroutine has already been implemented for you, so you do not need to write it yourself. But please understand what this subroutine does because you will have to call it later in your code. 3.8 wordProcess You’re almost done with the project (yay!!!), but there’s one more subroutine you need to write which uses the subroutines you’ve written so far. We will also use IO to take in user input and print the output for this subroutine. This subroutine will be called by the main subroutine. This is how this subroutine should work: • getInput: Reads all the characters input by the user until ’$$’ and stores it in a buffer in memory, labeled as BUFFER1. In memory, you should not store the ’$$’, but you should terminate the input provided by the user with the null character . • parseLines: For each word in BUFFER1, calculate the length of the word and add to BUFFER2 according to this: – If the word length + the current length of the line is less than 8, then fill in spaces in the line until line length = 8, then add newline char (all into BUFFER2). Note that spaces in between words count towards the line length. – To copy the words in BUFFER1 into BUFFER2 use the memcpy subroutine. – For the purpose of this this project, this subroutine assumes that ALL words inputted will have a maximum of 8 characters. • For each line resulting from the above operation, read an option number from the console: – If 1: Capitalize the line – If 2: Reverse each word in the line – If 3: Right justify the line – Else: Leave the line as it is • Print the result on the console • Exit As always, please do not modify the .orig address as it will cause issues in the autograder. Suggested Pseudocode:def wordProcess(): GetInput(x8000) OUT( ) ParseLines(x8000, x8500) startOfCurrLine = x8500 PUTS(“Enter modifier options. “) while (true): option = GETC() if (option == ’0’): pass elif (option == ’1’): CapitalizeLine(startOfCurrLine) elif (option == ’2’): ReverseWords(startOfCurrLine) elif (option == ’3’): RightJustify(startOfCurrLine) else: continue i = 0 while (i < 9): OUT(mem[startOfCurrLine]) startOfCurrLine++ i++ if (mem[startOfCurrLine – 1] == ’’): break return 3.9 Putting it all together: main This subroutine is our main subroutine, which is going to call wordProcess(). Since one of your subroutines uses the stack, it has been initialized at the beginning of this subroutine. The stack address has been loaded into R6 for you. You can also test your various subroutines by changing the address of the subroutine for debugging. Please follow the comments in the assembly file for this subroutine. 4 Deliverables Note: Please do not wait until the last minute to run/test your project, history has proved that last minute turn-ins will result in long queue times for grading on Gradescope. You have been warned. 5 Debugging When you turn in your files on Gradescope for the first time, you might not receive a perfect score. Does this mean you change one line and spam Gradescope until you get a 100? No! You can use LC3 Tools to step through each line in your assembly program to see if the program is behaving the way it’s supposed to. If one of your subroutines is not working, you should try to debug it in isolation to other subroutines. Here’s how to do so: 1. In your main function, the following lines jump/call a subroutine LD R5, SUBROUTINE_ADDR JSRR R5 To jump the subroutine you want to test, you need to change the value at the label SUBROUTINE ADDR to the address of the subroutine you want to test. 2. Also, remember that we are passing in arguments to each function through registers. So before you jump to the subroutine, make sure you put the correct values into the registers. The description for each subroutine contains which register to use as arguments. 3. Finally, you can load your file into LC3 Tools, assemble it and step through line-by-line to see why your subroutine is not behaving the way it should. Some other points to keep in mind: The Halt instruction resets your register values. To prevent this, you can do one of two things: 1. You can set a break point before returning from the subroutine. 2. Click on setting and turn on ”Stop Execution on reaching HALT”. 6 LC-3 Assembly Programming Requirements 6.1 Overview 1. Your code must assemble with NO WARNINGS OR ERRORS. To assemble your program, open the file with LC3Tools. It will complain if there are any issues. If your code does not assemble you WILL get a zero for that file. 2. Comment your code! This is especially important in assembly, because it’s much harder to interpret what is happening later, and you’ll be glad you left yourself notes on what certain instructions are contributing to the code. Comment things like what registers are being used for and what less intuitive lines of code are actually doing. To comment code in LC-3 assembly just type a semicolon (;), and the rest of that line will be a comment. 3. Avoid stating the obvious in your comments, it doesn’t help in understanding what the code is doing. Good Comment ADD R3, R3, -1 ; counter– BRp LOOP ; if counter == 0 don’t loop again Bad Comment ADD R3, R3, -1 ; Decrement R3 BRp LOOP ; Branch to LOOP if positive 4. DO NOT assume that ANYTHING in the LC-3 is already zero. Treat the machine as if your program was loaded into a machine with random values stored in the memory and register file. 5. Do NOT execute any data as if it were an instruction (meaning you should put .fills after HALT or RET). 6. Do not add any comments beginning with @plugin or change any comments of this kind. 7. Test your assembly. Don’t just assume it works and turn it in. 7 Rules and Regulations 7.1 General Rules 2. Please read the assignment in its entirety before asking questions. 4. If you find any problems with the assignment, it would be greatly appreciated if you reported them to the author (which can be found at the top of the assignment). Announcements will be posted if the assignment changes. 7.2 Submission Conventions 1. In order to submit your assignment, submit the files individually to the Gradescope assignment. 2. Do not submit links to files. The autograder does not understand it, and we will not manually grade assignments submitted this way as it is easy to change the files after the submission period ends. 7.3 Submission Guidelines 2. You are also responsible for ensuring that what you turned in is what you meant to turn in. After submitting you should be sure to download your submission into a brand new folder and test if it works. No excuses if you submit the wrong files, what you turn in is what we grade. In addition, your assignment must be turned in via Gradescope. Under no circumstances whatsoever we will accept any email submission of an assignment. Note: if you were granted an extension you will still turn in the assignment over Gradescope. 3. Projects turned in late receive partial credit within the first 48 hours, as defined in the syllabus. Between 0 and 24 hours late, you can receive a maximum score of 70%. Between 24 and 48 hours late, you can receive a maximum score of 50%. We will not accept projects turned in over 48 hours late. 7.4 Is collaboration allowed? From the syllabus: 7.5 Syllabus Excerpt on Academic Misconduct The goal of all assignments in CS 2110 is for you to learn. Learning requires thought and hard work. Copying answers thus prevents learning. More importantly, it gives an unfair advantage over students who do the work and follow the rules. 4. Publishing your assignments on public repositories, github, etc, that is accessible to other students is unauthorized collaboration and thus Academic Misconduct. 5. Suspected Academic Misconduct will be reported to the Division of Student Life Office of Student Integrity. It will be prosecuted to the full extent of Institute policies. 6. Students suspected of Academic Misconduct are informed at the end of the semester. Suspects receive an Incomplete final grade until the issue is resolved. 7. We use accepted forensic techniques to determine whether there is copying of a coding assignment. 8. Submitting an assignment with code or text from an AI assistant (e.g., ChatGPT) is academic misconduct. Anything you did not write in your assignment will be treated as an academic misconduct case. If you are unsure where the line is between collaborating with AI and copying AI, we recommend the following heuristics: Heuristic 1: Never hit “Copy” within your conversation with an AI assistant. You can copy your own work into your own conversation, but do not copy anything from the conversation back into your assignment. Instead, use your interaction with the AI assistant as a learning experience, then let your assignment reflect your improved understanding. Heuristic 2: Do not have your assignment and the AI agent open at the same time. Similar to the above, use your conversation with the AI as a learning experience, then close the interaction down, open your assignment, and let your assignment reflect your revised knowledge. This heuristic includes avoiding using AI directly integrated into your composition environment: just as you should not let a classmate write content or code directly into your submission, so also you should avoid using tools that directly add content to your submission. Deviating from these heuristics does not automatically qualify as academic misconduct; however, following these heuristics essentially guarantees your collaboration will not cross the line into misconduct.
1 Introduction 2 Setup The software you will be using for this project and all future circuit based assignments is called CircuitSim – an interactive circuit simulation package. CircuitSim is a powerful simulation tool designed for educational use. This gives it the advantage of being a little more forgiving than some of the more commercial simulators. However, it still requires some time and effort to be able to use the program efficiently. Please follow the instructions in the file ”CircuitSim Installation Guide.pdf” in Canvas, under ”Files > Course Software > CircuitSim” to install CircuitSim. All .sim files should be opened in CircuitSim. 3 Part 1 — Introduction to CircuitSim The first part of this project is designed to get you up to speed with CircuitSim. If you do not have CircuitSim downloaded and running, see the setup section of this document to get there. 3.1 Read Resources Read through the following resources • CircuitSim Wires Documentation https://ra4king.github.io/CircuitSim/docs/wires/ • Tutorial 0: My First Circuit https://ra4king.github.io/CircuitSim/tutorial/tut-1-beginner 3.2 Complete Tutorial 1 In the existing file tutorial1.sim and subcircuit Tutorial 1, complete the following tutorial. Do not rename the subcircuit or file. Be sure to label your two inputs a and b, and your output as c. Complete Tutorial 1 https://ra4king.github.io/CircuitSim/tutorial/tut-2-xor 3.3 Complete Tutorial 2 In the existing file tutorial2.sim and subcircuit Tutorial 2, complete the following tutorial. Do not rename the file or subcircuit. Name the input in, and the output out. Complete Tutorial 2 https://ra4king.github.io/CircuitSim/tutorial/tut-3-tunnels-splitters 4 Part 2 — ALU Now that we have the basics down, we can move on to more complex circuits and logic. All computer processors have a very important component known as the Arithmetic Logic Unit (ALU). This component allows the computer to do, as the name suggests, arithmetic and logical operations. For this part, you’re going to build an ALU of your own, along with creating some of the gates. For this part of the project you will: 1. Create the standard logic gates (NAND, NOR, NOT, AND, OR) 2. Create an 8-input multiplexer and an 8-output decoder 3. Create a 1-bit full adder 4. Create an 8-bit full adder using your 1-bit full adder 5. Use your 8-bit full adder and other components to construct an 8-bit ALU When building these circuits, restrictions have been placed on what you can use. These restrictions are listed at the beginning of each section. Using anything not listed will result in heavy deductions. You also need to have everything in its correctly named sub-circuit. More information on the sub-circuits is given below. Use tunnels where necessary to make your designs more readable, but do not overdo it! For gates, multiplexers, decoders, and adders you can often make clean circuits by placing your components strategically rather than using tunnels everywhere. Throughout this assignment, do not change/delete any of the input/output pins (You can move them). 4.1 1-Bit Logic Gates Allowed Components: Wiring Tab and Circuits Tab All of the circuits are found in the gates.sim file. For this part, you will create a transistor-level implementation of the NAND, NOT, NOR, AND, and OR logic gates. Remember for this section that you are only allowed to use the components listed in the Wiring section, along with any of the logic gates you are implementing in CircuitSim. For example, once you implement the NOT gate you are free to use that subcircuit in implementing other logic gates. Implementing the gates in the order of the subcircuit tabs can be the easiest option. All of the logic gates must be within their named sub-circuits. 4.2 Muxes Allowed Components: Wiring Tab, Gates Tab, and Circuits Tab All of the circuits are found in the muxes.sim file. 4.2.1 Decoder The decoder you will be creating has a single 3-bit selection input (SEL), and eight 1-bit outputs (labeled A, B, C, …, H). The decoder uses the SEL input to raise a specific output line. 000 should correspond to A, 001 should correspond to B, etc. 4.2.2 Multiplexer, commonly abbreviated as ”mux” The multiplexer you will be creating has 8 1-bit inputs (labeled appropriately as A, B, C, …, H), a single 3-bit selection input (SEL), and one 1-bit output (OUT). The multiplexer uses the SEL input to choose a specific input line for forwarding to the output. 000 should correspond to A, 001 should correspond to B, etc. 4.3 Adders Allowed Components: Wiring Tab, Gates Tab, and Circuits Tab All of the circuits are found in the alu.sim file. Throughout this assignment, you do not need to account for overflow. 4.3.1 1-Bit Adder The full adder has three 1-bit inputs (A, B, and CIN), and two 1-bit outputs (SUM and COUT). The full adder adds A + B + CIN and places the sum in SUM and the carry-out in COUT. For example: A = 0, B = 1, CIN = 0 ==> SUM = 1, COUT = 0 A = 1, B = 0, CIN = 1 ==> SUM = 0, COUT = 1 Hint: Making a truth table of the inputs will help you. 4.3.2 8-Bit Adder You should daisy-chain 8 of your 1-bit full adders together in order to make an 8-bit full adder. This circuit should have two 8-bit inputs (A and B) for the numbers you’re adding, and one 1-bit input for CIN. The reason for the CIN has to do with using the adder for purposes other than adding the two inputs. There should be one 8-bit output for SUM and one 1-bit output for COUT. 4.4 8-Bit ALU Allowed Components: Wiring Tab, Gates Tab, Plexer Tab, and Circuits Tab 000 add [A + B] 001 sub [A – B] 010 min [min(A, B)] 011 mysteryFunction See below 100 mostSignificantOne See below 101 isMultipleOf32 [A % 32 == 0] 110 multiplyByNegative7 [A * -7] 111 isPositive [A > 0] Remember, do NOT account for overflow. isMultipleof32 and isPositive should return either 00000000 for false or 00000001 for true. mysteryFunction: For this operation, you will need to implement a circuit which calculates the result of the following formula for input A: wordsize −⌊log2A⌋− 1. Note: For this function, the input can be treated as unsigned. Edge Case: When A = 0, the output of this function should be equal to the wordsize. Hint: Try applying this formula to the first 16 non-negative integers (0-15) using a wordsize of 4. Look for a pattern. Examples: A = 00011001 => return 00000011 (3) A = 00000111 => return 00000101 (5) mostSignificantOne: To elaborate, this operation should return the 8-bit representation of the value that is produced when all bits of A are cleared except for the most significant 1. Examples: A = 01100110 => return 01000000 A = 00001100 => return 00001000 Notice that mysteryFunction, mostSignificantOne, isMultipleof32, multiplyByNegative7, and isPositive only operate on the A input. They should NOT rely on B being a particular value. This ALU has two 8-bit inputs (A and B) and one 3-bit input for OP, which is the op-code for the operation in the list above. It has one 8-bit output named OUT. The provided autograder will check the op-codes according to the order listed above (add (000), sub (001), etc.) and thus it is important that the operations are in this exact order. If you ever need a constant value, use a constant pin (not an input pin). Failing to do so will interfere with the autograder. As always, do not change/delete any of the input/output pins (You can move them). 5 Part 3 — Advanced Combinational Logic All of the circuits are found in the project.sim file. For this part of the assignment, you are tasked with creating a sum of products circuit such that its behavior matches the expected behavior outlined by the truth table found in the truthtable kmap.xlsx spreadsheet. In order to do so, you should use the techniques taught in class to create and reduce boolean expression (see 5.1 below). As always, do not change/delete any of the input/output pins (You can move them). 5.1 Karnaugh Maps While it is not a deliverable, making 2 K-maps and reducing boolean expressions will make this circuit significantly easier to design. To aid this, we have provided a template for both K-maps below and in the truthtable kmap.xlsx spreadsheet: A B′C′ B′C BC BC′ A′ B′C′ B′C BC BC′ D′E′ D′E′ D′E D′E DE DE DE′ DE′ Note: The truthtable kmap.xlsx spreadsheet is NOT a deliverable. It only contains the truthtable that you need to use and sample K-Map templates. 5.2 Boolean Logic Details For this part of the project, we are asking that you approach this problem in sum of products format. This means that after your reductions using the K-maps, you should have something in the format OUT = A′B + C before attempting to build the circuit. Failure to do so can lead to complications in your circuit that prevent the reduction we are looking for. 5.3 Circuit Details To prevent trivialization of this assignment, we have placed a few restrictions: • All of this circuit should be contained in the project.sim file • You should try to reduce the amount of AND and OR gates as much as possible. Hint: The K-maps do this for you! 6 Autograder To run the autograder, run java -jar project1-tester-1.0.jar at a command prompt in the same directory as all your .sim files. This is the same autograder that Gradescope uses, but is much easier and faster to use. The autograder should be run from the terminal. 7 Deliverables Please submit the follow files: 1. tutorial1.sim 2. tutorial2.sim 3. gates.sim NOT, NAND, NOR, AND, OR 4. muxes.sim Decoder, MUX 5. alu.sim 1-Bit Adder, 8-Bit Adder, 8-Bit ALU 6. project.sim Advanced Combinational Logic to Gradescope under the assignment “Project 1 – Digital Logic”. 8 Rules and Regulations 8.1 General Rules 2. Please read the assignment in its entirety before asking questions. 4. If you find any problems with the assignment, it would be greatly appreciated if you reported them tothe author (which can be found at the top of the assignment). Announcements will be posted if the assignment changes. 8.2 Submission Conventions 1. In order to submit your assignment, submit the files individually to the Gradescope assignment. 2. Do not submit links to files. The autograder does not understand it, and we will not manually gradeassignments submitted this way as it is easy to change the files after the submission period ends. 8.3 Submission Guidelines 2. You are also responsible for ensuring that what you turned in is what you meant to turn in. Aftersubmitting you should be sure to download your submission into a brand new folder and test if it works. No excuses if you submit the wrong files, what you turn in is what we grade. In addition, your assignment must be turned in via Gradescope. Under no circumstances whatsoever we will accept any email submission of an assignment. Note: if you were granted an extension you will still turn in the assignment over Gradescope. 3. Projects turned in late receive partial credit within the first 48 hours, as defined in the syllabus.Between 0 and 24 hours late, you can receive a maximum score of 70%. Between 24 and 48 hours late, you can receive a maximum score of 50%. We will not accept projects turned in over 48 hours late. 8.4 Is collaboration allowed? From the syllabus: 8.5 Syllabus Excerpt on Academic Misconduct The goal of all assignments in CS 2110 is for you to learn. Learning requires thought and hard work. Copying answers thus prevents learning. More importantly, it gives an unfair advantage over students who do the work and follow the rules. 3. Using code from GitHub, via Googling, from Stack Overflow, etc., is Academic Misconduct (HonorCode: Academic Misconduct includes “submission of material that is wholly or substantially identical to that created or published by another person or persons”). 4. Publishing your assignments on public repositories, github, etc, that is accessible to other students isunauthorized collaboration and thus Academic Misconduct. 5. Suspected Academic Misconduct will be reported to the Division of Student Life Office of StudentIntegrity. It will be prosecuted to the full extent of Institute policies. 6. Students suspected of Academic Misconduct are informed at the end of the semester. Suspects receive an Incomplete final grade until the issue is resolved. 7. We use accepted forensic techniques to determine whether there is copying of a coding assignment. 8. Submitting an assignment with code or text from an AI assistant (e.g., ChatGPT) is academic misconduct. Anything you did not write in your assignment will be treated as an academic misconduct case. If you are unsure where the line is between collaborating with AI and copying AI, we recommend the following heuristics: Heuristic 1: Never hit “Copy” within your conversation with an AI assistant. You can copy your own work into your own conversation, but do not copy anything from the conversation back into your assignment. Instead, use your interaction with the AI assistant as a learning experience, then let your assignment reflect your improved understanding. Heuristic 2: Do not have your assignment and the AI agent open at the same time. Similar to the above, use your conversation with the AI as a learning experience, then close the interaction down, open your assignment, and let your assignment reflect your revised knowledge. This heuristic includes avoiding using AI directly integrated into your composition environment: just as you should not let a classmate write content or code directly into your submission, so also you should avoid using tools that directly add content to your submission. Deviating from these heuristics does not automatically qualify as academic misconduct; however, following these heuristics essentially guarantees your collaboration will not cross the line into misconduct.
Team project of CS2x1:Data Structures and Algorithms at IIT Dharwad Problem statement You are a lumberjack in a roadside forest. Every day you would like to cut down trees of the maximum value in the limited time that you have. We represent a forest as a rectangular grid of dimensions n by n points. Each edge between the neighboring grid points has a length of 1. At the position of each point, there could be a tree. Each tree is described using the following parameters: height h thickness d unit weight c unit value p We calculate the value of each tree according to the formula: p · h · d. To cut down the tree, you have to reach it first. You can move only along the edges between the neighboring grid points. To cut down the tree at the position that you occupy you have to select one of four directions (along grid lines) in which the tree will fall. At the beginning of the day, you start in the lower-left corner of the forest, which is located at the point (0,0). You can assume that there is no tree there. If the tree that you cut falls on the other tree, which is lighter than the one that is falling, then this tree will also fall without being cut directly. We say that the tree is heavier if the total weight calculated as c · d · h is greater than the total weight of the second tree. In this way, one can achieve a domino effect by pushing one tree onto another. We assume that a tree falls on the other when the distance between them is less the height of this tree. Weights of trees do not cumulate – we always take into account only the weight of the tree, which directly fell onto another. If for example tree A falls onto tree B and its weight is greater than weight of tree B then it can push tree B onto another tree C located in the same direction if the distance between B and C is smaller to height of B and, moreover, tree C is lighter than tree B. When comparing trees B and C we do not take into account tree A that lays on tree B. Moreover, if tree B is not lighter than tree A then it blocks tree A and it will not have a chance to fall onto tree C. Calculate the biggest profit that you can reach during t time units and provide a corresponding sequence of movements. Assume that the walk between the two neighboring grid points takes 1 unit of time, and cutting the tree takes d units of time. Input The first line of input contains three integers: 0 < t
Lab #5: Making Function Calls [ This document is available on Canvas and course website http://www.comp.nus.edu.sg/~cs2100 ]Note: Objective In this lab, you will use QtSpim to explore the idea of function calls in MIPS Assembly Code. This document and its associated files (sayHi.asm and arrayFunction.asm) can be downloaded from Canvas or the CS2100 course website. Just like any high-level programming language, modularization (separating code into welldefined procedures/functions) is an important idea for assembly programming. Conceptually, making function call is actually simple: we need to “jump” to another portion of code (the function body) then start executing the instructions in the function body. When we reach the end of that function, another “jump” is needed to go back to the caller. 0x3024 #Body of Function F 0x3028 #Body of Function F 0x302C #Done! Jump back to callerSo, the simplest kind of function call can be accomplished by just two “jump” instructions! To facilitate function calls, MIPS gives us two variants of the “j” instructions, the “jal” (jumpand-link) and the “jr” (jump by register). Don’t worry, they are much easier than the name suggested. First, download and load the assembly program “sayHi.asm” in QtSpim. The original content of the file is given on the next page. # sayHi.asm .data str1: .asciiz “Before function ” str2: .asciiz “After function ” str3: .asciiz “Inside function: Say Hi! ” .text main: li $v0, 4 # system call code for print_string la $a0, str1 # address of string to print syscall # print the stringjal sayHi # Make a function call to sayHi()li $v0, 4 # system call code for print_string la $a0, str2 # address of string to print syscall # print the string# End of main, make a syscall to “exit” li $v0, 10 # system call code for exit syscall # terminate program# start of function sayHi() sayHi: li $v0, 4 # system call code for print_string la $a0, str3 # address of string to print syscall # print the string # Use “jr” to go back to callerThe intention of the program is to print 3 messages in the following order:The first and third messages are printed in the “main” function while the second message is printed by the “sayHi” function. The given program is almost complete, with only one missing instruction. The purpose of this code is to demonstrate the necessary instructions needed for making a function call. Now, let us step through the program to make several observations. Use the “Single Step” button or press F10 to go through the program line by line. Stop when you reach the instruction “jal sayHi”.Answer: The instruction address of “jal sayHi” is at 0x_______________Press F10 one more time to execute the “jal” instruction. Answer the following:Answer: The PC is now at 0x_______________ Answer: The register $31 now contains 0x_______________ At this point, you should be able to see why the name of register $31 is $ra (return address). Express the content of register $31 with respect to the instruction address of the corresponding “jal” instruction. Use the notation Addr(jal) to indicate the instruction address of “jal” instruction.Answer: $31 = _______________________If you continue stepping through, we will reach the end of the “sayHi” function and get ‘stuck’. We need a way to go back to the main function and continue from where we left off. We can do this easily by the “jr” (jump by register) instruction which is missing in the program. This “jr” instruction takes a register number as operand. It will jump to the address stored in the specified register. For example, jr $15 The content of register $15 will be used as the target address. This is known as direct addressing (the address is directly specified in full). What is the correct register number to be used in the “jr” instruction so that we can jump back to main? Answer: jr ______Now, edit your code and insert the “jr” instruction accordingly. Run your program, you should see the 3 messages in the same order as shown in the earlier output screenshot.We can now turn to other aspects of function call, namely function parameters (arguments) and function return value. Actually, we have encountered this idea in previous labs. Take a look at this very familiar sequence of using the system call read_int: li $v0, 5 # System call code for read_int syscall sw $v0, 0($t1) # “return result” is in $v0You can see that there is an agreement to use the register $v0 to store the system call code for the system call (a special kind of function call). Additionally, the return result (an integer read from user) is placed in register $v0 when the system call is completed. Key idea: we can pass information to the function by placing values in registers and retrieve the return result in the same way.Let us first attempt to pass information to a function. Download and load the arrayFunction.asm in QtSpim. The main function code is given below (this is not the whole content; see the file for the complete content): .data array: .word 8, 2, 1, 6, 9, 7, 3, 5, 0, 4 newl: .asciiz ” ”.text main: # Print the original content of array # setup the parameter(s) # call the printArray function# Ask the user for two indices li $v0, 5 # System call code for read_int syscall addi $t0, $v0, 0 # first user input in $t0li $v0, 5 # System call code for read_int syscall addi $t1, $v0, 0 # second user input in $t1# Call the findMin function # setup the parameter(s) # call the function# Print the min item # Calculate and print the index of min item # End of main, make a syscall to “exit” li $v0, 10 # system call code for exit syscall # terminate programThe basic flow of the program is as follows: 1. Print the original content of array. 2. Ask the user for two indices X and Y, where X Y. 3. Find the minimum item between A[X] and A[Y] (inclusive). 4. Print the minimum item and the index of the minimum item. You’ll need to code for parts 1, 3 and 4. Again, don’t panic as most of the code are already written! For part 1, the following function is already given in the program: ### Function printArray ### # Input: Array Address in $a0, Number of elements in $a1 # Output: None # Purpose: Print array elements # Registers used: $t0, $t1, $t2, $t3 # Assumption: Array element is word size (4-byte) printArray: addi $t1, $a0, 0 # $t1 is the pointer to the item sll $t2, $a1, 2 # $t2 is the offset beyond the last item add $t2, $a0, $t2 # $t2 is pointing beyond the last item loop: beq $t1, $t2, end lw $t3, 0($t1) # $t3 is the current item li $v0, 1 # system call code for print_int addi $a0, $t3, 0 # integer to print syscall # print it addi $t1, $t1, 4 j loop # Another iteration end: li $v0, 4 # system call code for print_string la $a0, newl # syscall # print newline jr $ra # return from this function The comments at the beginning of the function give you a good idea of how to make use of this function. Pay special attention to the “input” information, which tells you where to place the expected parameters. Without changing this function, complete the first part of the main program. You only need to place the correct information in the registers $a0 and $a1 then make a function call. Test your program, and you should see the original content of array printed on screen. (Hint: Don’t forget the use of “li” and “la” instructions). Now, let’s tackle something slightly more challenging. Let us now write a function to find the minimum element. The function header is given in the program as follows: ################################################################# # ### Function findMin ### # Input: Lower Array Pointer in $a0, Higher Array Pointer in $a1 # Output: $v0 contains the address of minimum item # Purpose: Find and return the minimum item # between $a0 and $a1 (inclusive) # Registers used: # Assumption: Array element is word size (4-byte), $a0
[ This document is available on Canvas and course website https://www.comp.nus.edu.sg/~cs2100 ]Objective In this lab, you will explore the QtSpim, a MIPS simulator available on Windows, Mac OS and Linux. This document and its associated files (sample1.asm, sample2.asm and sample3.asm) are all available on Canvas and the course website.Software and Documentation The following resources are available on the CS2100 website → “Resources” → “Online”, or https://www.comp.nus.edu.sg/~cs2100/2_resources/online.html directly. 1. QtSpim software: Download the correct QtSpim for your platform (either Windows or MacOS). Follow the installation instructions to install QtSpim in your system. In the lab, QtSpim for Windows has already been installed on the computers.See https://support.apple.com/en-sg/guide/mac-help/mh40616/mac for how to get around this. 2. Assemblers, Linkers, and the SPIM Simulator documentation: An overview and reference manual for SPIM and MIPS32 instruction set. The sections that you should definitely read are Section A.9 (SPIM) and Section A.10 (MIPS R2000 Assembly Language). This document can also be found in the “Computer Organization and Design” reference book as Appendix A (3rd edition and before) or Appendix B (4th Edition). Note that the SPIM discussion is based on the older version of the simulator. Although there is significant change in the looks (UI) of the simulator, the underlying mechanism and information are largely intact.Introduction SPIM, which is just MIPS spelled backwards, is a software that simulates the working of a MIPS processor. It is capable of running MIPS32 assembly language programs and it allows user to inspect the various internal information of a MIPS processor. SPIM is a self-contained system for running MIPS programs. It contains a debugger and provides a few operating system–like services. SPIM is much slower – 100 or more times! – than a real computer. The most current version of SPIM is known as QtSpim which is basically the simulator SPIM with the Qt GUI framework on top. QtSpim is cross-platform and currently available for Windows, Mac OS and Debian Linux.My First MIPS Program: sample1.asmBEFORE YOU BEGIN, please read the (very) frequently asked question below. FAQ: I ran the code and encountered this “Exception occurred at PC = 0x00000000” error, what should I do? Answer: Your QtSpim is not using address 0x00400000 as the default start address of your code. Click on “Simulator → Run Parameters” and change the value under “Address or label to start running program” from 0x00000000 to 0x00400000.Let’s give it a try! Before you start, make sure you have downloaded the 3 assembly programs sample1.asm, sample2.asm and sample3.asm from Canvas or the course website to a working directory of your choice. Click on the QtSpim shortcut at the desktop to invoke QtSpim. You should see a screen similar to the following:Let’s check that we have the right simulator configuration for the labs. Click on “Simulator → Settings” (or QtSpim->Preferences on Macs) on the menu bar. Go to the “MIPS” tab then: 1. Click the “Simple Machine” button to use the simplest setting for the processor simulation. 2. Uncheck the “Load Exception Handler”.Click “OK” to save your setting. Go to “File → Reinitialize and Load File” and select sample1.asm from your working directory. With the settings mentioned, your QtSpim window should look exactly the same as follows:The display is divided into three frames: Registers, Text Segment and Messages. ▪ Registers frame: This window shows the values of special and integer registers in the MIPS CPU. There is a tab for FPU (floating point unit) registers, which you can safely ignore. ▪ Messages frame: This is where QtSpim writes messages and where error messages appear. Note that the Text Segment Frame can change to display the Data Segment by clicking on the “Data” tab. The data segment represents the data your program loaded into the “main memory”, we’ll see more of this later. Besides the above, there is also a separate Console window for input and output. If the Console window is hidden, you can click “Windows → Console” to enable it. Let us now take a look at sample1.asm:# sample1.asm .text main: addi $t1, $zero, 97 li $v0, 10 syscalladdi $9, $0, 97 ; 3: addi $t1, $zero, 97 ori $2, $0, 10 ; 4: li $v0, 10 syscall ; 5: syscallThe first line is a comment line, which begins with “#”. The second line .text is the assembler directive that specifies the starting address of the source code. If no starting address is specified, the default value 0x00400000 will be assumed. The next line contains a MIPS instruction: the add immediate (addi) instruction will place the addition result (0 + 97), i.e. decimal value 97, into register $t1. Numbers are decimal (base 10) by default. If they are preceded by 0x, they are interpreted as hexadecimal (base 16). For example, 256 and 0x100 denote the same value. In QtSpim, the registers $t1 and $zero are translated into their respective numbered registers $9 and $0. Observe the value of register $t1 (register 9) and the value of PC (program counter) in the Registers window. They are both zero at the moment. The next two lines li $v0, 10 and syscall constitute a system call to exit. The line li $v0, 10 is a pseudo-instruction (li = load immediate) that is translated into ori $2, $0, 10. This will be explained in the next section and we will ignore them here. If you want to make any modification to sample1.asm, you can use any text editor such as NotePad, etc. After modification, you need to reload it with “File → Load File”.Now click on the “Single Step” button to execute one assembly statement.You should see the changes to the PC and $t1 register in the register frame. What number base is the value in register $t1? Answer: _________________________.Text Segment Frame Now, take a closer look at the text segment frame:For each line, ▪ the first column – [0x00400024] – is the memory location (address) of the instruction; (the default starting address is 0x00400000; some lines of code are inserted before your code by the system, hence your code starts at 0x00400024) ▪ the second column – 0x20090061 – is the encoded instruction in hexadecimal; ▪ the third column – addi $9, $0, 97 – is the native code; and ▪ the fourth column – addi $t1, $zero, 97 – is your source code. Everything after the semicolon is the actual line from your source code. The number “3:” refers to the line number of the corresponding MIPS instruction in the source code. Sometimes there is nothing after the semicolon. This means that the instruction was produced by QtSpim as part of translating a pseudo-instruction into more than one real MIPS instruction.Running and Stepping through Code You can control the execution by choosing different modes. “Run/Continue”: Executes until (program ends / error occurs / user pause / user stop)Setting Value into a Register “Change Register Contents” to assign value directly into that register. Try to change the value of R16 (which is $16 or $s0) to decimal value 100 (or hexadecimal 64).Writing a message: sample2.asm Download sample2.asm into your working directory. Click on “File” → “Reinitialize and Load File” to open this file. The content of sample2.asm is shown below: # sample2.asm .data 0x10000100 msg: .asciiz “Hello” .text main: li $v0, 4 la $a0, msg syscall li $v0, 10 syscallYou will notice that there are a couple of special names starting with a period, e.g. “.data”, “.text” etc. These are assembler directives that tell the assembler how to translate a program but do not produce machine instructions. The second line .data directive specifies the starting address (0x10000100) of the data (in this case, the string “Hello”). The .asciiz directive stores a null-terminated string (a string that ends with a null character) in memory. For your reference, the set of directives that will be used in the lab exercises is given in the Appendix. The first two statements are both pseudo-instructions: ▪ Load immediate (A-57 in Appendix A): li rdest, imm # load the immediate imm into register rdest. ▪ Load address (A-66 in Appendix A): la rdest, address # load computed address – not the contents of the location – into register rdest. The syscall instruction makes a system call, and the value in register $v0 indicates the type of call. The value 4 in $v0 indicates a print_string call (A-43 to A-43 in Appendix A: System Calls), and the string to be printed is indicated by $a0. The value 10 in $v0 indicates an exit call. We will explore more about system calls in the next lab.Click on the “Data” tab on the Text Segment frame to display the Data Segment. Take a close look at the content of memory address 0x10000100:Can you figure out where and how is the string “Hello” stored? Write out the ASCII values, in hexadecimal form, of the characters ‘H’, ‘e’, ‘l’ and ‘o’ below: ‘H’: ____ ‘e’: ____ ‘l’: ____ ‘o’: ____Now, run the program (press the “Run/Continue” button). What do you see on the Console window? As mentioned before, you can ignore the “Attempt to execute non-instruction ….” error message for now. Answer: ________________Modifying a message: sample3.asm Download sample3.asm into your working directory. Click on “File” → “Reinitialize and Load File” to open this file. The file is the same as sample2.asm at this point except a few comments added near the end of the main routine. We are going to edit the program to perform some simple tasks.First, take some time to check your understanding of the li (load immediate) and la (load address) pseudo-instructions. Use the “Single Step” button to step through the program. Stop at the line “syscall”. What do you see in the register $v0 and $a0 at this point?Answer: $v0 = _____________ $a0 = ____________________Let us now read a single character (i.e. single byte) from the string into a register. Edit the given program sample3.asm as described below:Add an instruction (lb – load byte) to load the value of ‘o’ (the last character in “Hello”) into register $t0. Add the instruction after the “syscall” instruction. What is the correct memory address to use? (Remember to save your edits, then reload the assembly file in QtSpim).Answer: lb $t0, ______________Now, we want to change the ‘o’ into ‘O’ (capital Oh). Let us first change the value in register $t0 by simple arithmetic. What is the difference in ASCII value between ‘o’ and ‘O’?Answer: _________Use the (addi – add immediate) instruction to change the value in $t0 to the ASCII value of ‘O’:Answer: addi ____________________Finally, let us put this back into the memory. Use the (sb – store byte) instruction to place the changed value of $t0 into the position ‘o’ (i.e. overwriting the value in memory). Take note of the change in data segment when you execute this instruction.Answer: sb ______________________Now, just make another syscall to print the string again. Add the instruction syscall at the end of the program as indicated by the comment. What do you see in the output when you run the program?Answer: _________________________Appendix
[ This document is available on Canvas and course website https://www.comp.nus.edu.sg/~cs2100 ]Special Note for Users Using MacOS on Apple Silicon The GDB debugger is unfortunately still unavailable for users of MacOS on Apple Silicon (M1/M2 based MacBooks, for example). If you are using MacOS on Apple Silicon, there are two main choices for you: https://lldb.llvm.org/use/tutorial.htmlC Arrays Array is a kind of data structure that can store a fixed-size sequential collection of elements of the same type. An array is used to store a collection of data, but it is often more useful to think of an array as a collection of variables of the same type.Instead of declaring individual variables, such as number0, number1… and number99, you declare one array variable such as numbers and use numbers[0], numbers[1], …, numbers[99] to represent individual variables. A specific element in an array is accessed by an index which starts from 0. All arrays consist of contiguous memory locations. The lowest address corresponds to the first element and the highest address to the last element.C Functions and Arrays In C programming, a single array element or an entire array can be passed to a function. A single value will be passed by value, whereas when passing the whole array, it is always passed as a pointer to the first element of the array.Objective: You will learn how to use arrays and functions in C.Preparation (before the lab): Please refer to lab#1 if you have not yet installed gdb on your system.Procedure: 1. Retrieve the lab2a.c and lab2b.c programs.2. Compile lab2a.c with gcc using the following command: gcc –o lab2a lab2a.c3. What is the output of the program? Can you change it to “2”? Note: The output should be related to the ageArray such as an element in ageArray.4. What is the purpose of the operator sizeof? What datatype will sizeof always give “1” value for on all architectures?5. Can you get the number of elements in ageArray? To produce the following output: 2 Size of the array is 4Modify the main function, write it below and show the output to your labTA. Note: The output “2” and size of array (i.e., 4 (four)) should be related to ageArray such as an element in ageArray and the number of elements in ageArray.6. Compile lab2b.c with gcc using the following command: gcc –o lab2b lab2b.c7. Can you give 2 ways of displaying the stored value and address value of the first element of an array?8. Can you define the function hexToDecimal(char hex[], size_t size) in the lab2b.c using pointers to traverse the array? Write your function below and show your labTA the output. Note: You are not allowed to use strtoul, strtol, or other functions from stdlib.h. Hint: Reading the hexadecimal numbers backwards might be easier. Furthermore, you are already given the function hexVal(char hex) to simplify your work.9. Why do we pass the size of the array to the hexToDecimal function in lab2b.c? Can we calculate the size of the array inside the function?10. What is the format specifier to print a variable of datatype size_t?Program lab2a.c #include void display(int); int main() { int ageArray[] = { 2, 15, 4, 23 }; display(ageArray[2]); return 0; }void display(int age) { printf(“%d “, age); }Program lab2b.c #include #include #include int hexToDecimal(char[], size_t); int hexVal(char);int main(void) { // As a basic requirement, translate just the first two-digit // hex number. As an extra exercise translate all digits. char hex[10]; size_t len;printf(“Enter up to 8 hexadecimal digits (e.g. 091A2C, etc): “); fgets(hex, 10, stdin); len = strlen(hex);/* End-of-Line Check */ if(hex[len-1] == ‘ ‘) { len = len – 1; hex[len] = ”; } printf(“You entered: %s “, hex); printf(“The value in decimal is: %d “, hexToDecimal(hex, len));return 0; } int hexVal(char hex) { switch(toupper(hex)) { case ‘0’: return 0; case ‘1’: return 1; case ‘2’: return 2; case ‘3’: return 3; case ‘4’: return 4; case ‘5’: return 5; case ‘6’: return 6; case ‘7’: return 7; case ‘8’: return 8; case ‘9’: return 9; case ‘A’: return 10; case ‘B’: return 11; case ‘C’: return 12; case ‘D’: return 13; case ‘E’: return 14; case ‘F’: return 15; } return 0; } int hexToDecimal(char hex[], size_t size) { // complete the function bodyreturn 0; }
In this assignment you are asked to write a program to maintain a playlist of songs with an option to display the playlist in alphabetical order by song title. Your program should also allow the addition of new songs to the playlist, the removal of songs, and to save the playlist in an external data file. You are required to use the binary tree data structure discussed in class. The Song Class Your playlist is based on Song objects. A Song object is defined by a title, an artist, and a rank number (from 1 to 5). The Song class implements the Comparable interface to allow Song objects to be compared to each other. The comparison is always done by the song titles. The BST Class The only methods that are left for you to implement in the BST class are the clearRecursively and clear methods. The clear method clears the binary tree, setting all left and right (binary) node references to null, also setting the root node of the tree to null. The PlayList Class The Playlist application assumes that the songs of the playlist are in a file named playlist.csv. This file has one song per line and each line is structured like the following: title, artist, and rank. Below is an example of a playlist.csv file: Take On Me,A-ha,4 Billie Jean,Michael Jackson,3 Another One Bites the Dust,Queen,5 Like a Prayer,Madonna,4 Africa,Toto,4 Every Breath You Take,The Police,4 Need You Tonight,INX,2 Don’t You Want Me,The Human League,4 Jump,Van Halen,3 Just Like Heaven,The Cure,5 The Playlist class defines an instance variable named bst that references a BST of songs (the playlist). Below is a brief description of the methods that are left for you to implement in Playlist: loadSongs: opens the csv file for reading and parses all songs into the (already instantiated) BST object (you must use the bst instance variable). saveSongs: opens the csv file for writing and iterates over the bst object, writing its songs into the csv file. addSong: read all information for a song (title, artist, and rank) and then add the song into the binary tree. clear: clears the bst after a confirmation from the user. searchSong: searches for a song in the playlist by title. removeSong: removes a song from the playlist given its title. Typical Run “` Welcome to my playlist! Options: 1:print 2:add 3:search 4:remove 5:clear 6:quit ? 1 [‘Take On Me’,’A-ha’, rank=4] [‘Billie Jean’,’Michael Jackson’, rank=3] [‘Another One Bites the Dust’,’Queen’, rank=5] [‘Africa’,’Toto’, rank=4] [‘Like a Prayer’,’Madonna’, rank=4] [‘Every Breath You Take’,’The Police’, rank=4] [‘Don’t You Want Me’,’The Human League’, rank=4] [‘Jump’,’Van Halen’, rank=3] [‘Just Like Heaven’,’The Cure’, rank=5] [‘Total Eclipse of the Heart’,’Bonnie Tyler’, rank=2] Options: 1:print 2:add 3:search 4:remove 5:clear 6:quit ? 2 Title? Need You Tonight Artist? INX Rank [1-5]? 2 Options: 1:print 2:add 3:search 4:remove 5:clear 6:quit ? 1 [‘Take On Me’,’A-ha’, rank=4] [‘Billie Jean’,’Michael Jackson’, rank=3] [‘Another One Bites the Dust’,’Queen’, rank=5] [‘Africa’,’Toto’, rank=4] [‘Like a Prayer’,’Madonna’, rank=4] [‘Every Breath You Take’,’The Police’, rank=4] [‘Don’t You Want Me’,’The Human League’, rank=4] [‘Jump’,’Van Halen’, rank=3] [‘Just Like Heaven’,’The Cure’, rank=5] [‘Need You Tonight’,’INX’, rank=2] [‘Total Eclipse of the Heart’,’Bonnie Tyler’, rank=2] Options: 1:print 2:add 3:search 4:remove 5:clear 6:quit ? 3 Title? Total Eclipse of the Heart A song with the title “Total Eclipse of the Heart” was found! Options: 1:print 2:add 3:search 4:remove 5:clear 6:quit ? 3 Title? With or Without You No song with the title “With or Without You” was found! Options: 1:print 2:add 3:search 4:remove 5:clear 6:quit ? 4 Title? Need You Tonight Options: 1:print 2:add 3:search 4:remove 5:clear 6:quit ? 1 [‘Take On Me’,’A-ha’, rank=4] [‘Billie Jean’,’Michael Jackson’, rank=3] [‘Another One Bites the Dust’,’Queen’, rank=5] [‘Africa’,’Toto’, rank=4] [‘Like a Prayer’,’Madonna’, rank=4] [‘Every Breath You Take’,’The Police’, rank=4] [‘Don’t You Want Me’,’The Human League’, rank=4] [‘Jump’,’Van Halen’, rank=3] [‘Just Like Heaven’,’The Cure’, rank=5] [‘Total Eclipse of the Heart’,’Bonnie Tyler’, rank=2] Options: 1:print 2:add 3:search 4:remove 5:clear 6:quit ? 6 Saving playlist changes… Done! Bye! “` Submission Zip the following files into playlist.zip: |__Song.java |__BST.java |__PlayList.java Submit your playlist.zip file on Canvas. Rubric +10 Song Class +5 constructor +5 compareTo +20 BST Class +15 clearRecursively +5 clear +70 PlayList Class +15 loadSongs +10 saveSongs +15 addSong +10 clear +10 searchSong +10 removeSong
[ This document is available on Canvas and course website https://www.comp.nus.edu.sg/~cs2100 ]_SPECIAL NOTE FOR APPLE SILICON MACOS USERS GDB does not work on MacOS on Apple Silicon (M1 or M2) MacBooks. If you are using an M1 or M2 based MacOS system, you have two choices: https://www.parallels.com/landingpage/pd/education/ ii) Use LLDB instead. The commands aren’t exactly the same, but you should be able to accomplish the steps below using equivalent commands, though it will be harder work for you. You can find an LLDB tutorial here: https://lldb.llvm.org/use/tutorial.htmlGNU Debugger (GDB) https://www.gnu.org/software/gdb/ A debugger is used to analyze program execution in a step-by-step and detailed manner. It is used to find bugs in a program. Using a debugger, we can execute a program partially and view the status of the variables and resources being used the program to identify any discrepancies. GDB is an open source, freely available debugger which can be used for multiple languages. GDB can do four main kinds of things (plus other things in support of these) to help you catch bugs in the act: • Start your program, specifying anything that might affect its behaviour. • Make your program stop on specified conditions. • Examine what has happened, when your program has stopped. • Change things in your program; so that you can experiment with correcting the effects of one bug and go on to learn about another.GNU Compiler Collection (GCC) GCC is an open-source compiler system used to compile C/C++ programs: https://gcc.gnu.org/ Objective: You will learn how to use GDB to debug a C program. Preparation (before the lab): 1. Install GDB: a. Ubuntu: sudo apt-get install gdb b. OSX: brew install gdb (Does not work on Apple Silicon. See special note above.) c. Windows: • Download Cygwin (https://cygwin.com/install.html)Note: The installer will ask you to choose a mirror to download from. If possible, choose https://download.nus.edu.sg. If this is not available, choose an Australian or US server as these are generally faster.• Select develop packages during installation:• Start Cygwin terminal from the start menu:2. Starting GDB (all platforms): Type GDB in the terminal (Cygwin terminal for windows users). Help command lists the help and quit command exits GDB.Procedure: 1. Download the file lab1.c from Canvas. 2. Compile lab1.c with gcc using the following command: gcc –g –o lab1 lab1.c 3. What is the purpose of the flags “g” and “o” in gcc?4. Execute the program you just compiled using the command: ./lab1 (for windows type: lab1). What is the error encountered (if any!)? Answer: ______________________________________________________5. Start the GDB debugger by using the command: gdb lab16. To run the program in GDB, you can use the command run. This will run the whole program without any pause. Type run to execute the program.7. To get into the debug mode use the start command• You can use the list command to view the source code at any point • You can also use layout src and layout asm commands to view source code and assembly code in a split screen.8. A breakpoint is a command to put an intentional pause in the program execution to inspect the variable values and resources in the program. You can set multiple breakpoints in a program. In GDB you can put a breakpoint at any line number using the command:> break lineNumber or > b lineNumberExample: This will put a breakpoint on line 6 > break 6Now if you run the program, it will pause at line 6. You can continue execution (till end or the next breakpoint) using the continue command.Which line(s) will you set the breakpoint(s) in?Answer: ___________________________________________________________9. A step command is used to carry out step-by-step execution of the program. You can step through the program using the following command:> step This will execute only the next line of code or > step numberOfLinesE.g. > step 3 will execute next three lines of code• You can “switch on” display of the associated assembly code related to the instruction being executed using the command: set disassemble-next-line on10. At every step (or breakpoint) you can view a variable value using the print command: > print aYou can view all local variable values using the command: > info localsWhat are the values of variables c and d at the start of line 8 (before executing line 8)? Answers: _______________________________________________________________11. You can view the register values at any step or breakpoint using this command: > info registers12. You can stop the debugging by using the stop command. To quit GDB, use the quit command.13. Debug and modify lab1.c to carry out four arithmetic operations (+, -, /, *) and print the days of the week. The output of the program should look as follows:The code lab1.c is also shown on the next page for your reference. Show your labTA the output of your corrected program.14. Submit this report to your labTA at the end of the lab. You do not need to submit the corrected program. You are not to email the report to your labTA.Program lab1.c #include int main(void){ int a = 10; int b = 10; int c = a+b; int d = a-b; int e = a/d; int f = a*b; int i; char *day[7] = { };printf(“Arithmetic operations: “); printf(“a+b = %d “, c); printf(“a-b = %d “, d); printf(“b/a = %d “, e); printf(“a*b = %d “, f);printf(“Days of the week: “); for (i=0; i
The N-Queens problem can be stated as: can you place n queens on a nxn board in such a way that no one attacks another queen? The problem is credited to Max Bezzel who first formulated the problem in 1848. N-Queens can be solved using a computational technique called exhaustive search which tests all possible solutions to a problem. In this project, you are asked to solve the N-Queens problem using exhaustive search optimized with tree pruning and backtracking. In summary, you will develop a program that will display all solutions for the N-Queens problem, given the value for n, also showing how many solutions were found at the end. The figure below shows one solution for a 8Queens instance of the problem.The ChessBoard Class The ChessBoard class models a chess board with a given size (parameter N of the problem), which should be in [4, 15]. If the size is not informed, its value defaults to 8. The actual board configuration is controlled using a 2D array of boolean. In this project we will use the convention: 1st dimension represents rows and 2nd dimension represents columns. Placing a queen at location means setting the board’s location to true. ChessBoard defines methods that are helpful to modify or verify the state of the chess board. They are described below (also in comments embedded in the code): size(): the size of the chess board (parameter N of the problem); setQueen(int i, int j): set a queen at location (i, j); hasQueen(int i, int j): checks if there is a queen at location (i, j); hasQueen(int i): checks if there is a queen at row i; isValid(): checks if the current configuration is valid (no queens attacking); isSolved(): checks if the current configuration is valid and it solves the problem (number of queens placed matches the problem’s size); queens(): the number of queens currently on the board; clone(): returns a new ChessBoard that has the exact same configuration of the current one. You are NOT allowed to change any of the ChessBoard’s interface (methods above). Your solution must use all methods above. However, you are free to add your own (private) methods as you find them useful. Two helper methods are suggested: checkDiagonals(): checks if the current configuration passes the diagonals test (no queens attacking on diagonals); checkRowsColumns(): checks if the current configuration passes the row/column test (no queens attacking on rows/columns). The ChessBoardTest Class SOME unit tests were provided. However, those tests are far from being comprehensive as they only do basic checks of the ChessBoard class. It is up to you to create your own tests to certify whether your class is ready to be used in NQueens. Feel free to share your ChessBoardTest class with your classmates. I will try to create more tests and share with you later. The ChessPanel Class This class implements the GUI for the board. The code is given to you. The only method that you will be using from this class is the following: updateChessBoard(ChessBoard chessBoard): updates the chess board as seen by the GUI. The NQueens Class The NQueens class is the application that solves the N-Queens problem. It starts by asking the user for the parameter N. Then it instantiates a NQueens object with the given size and calls its run method, which implements the exhaustive search algorithm to solve the problem, showing each chess board configuration on the GUI, pausing SLEEP_TIMEms between configurations and returning the total number of chess board configurations found. The exhaustive search algorithm was explained in class. But basically you need to create a stack of ChessBoard objects and then push size ChessBoard objects, each of then placing a queen at a different column (or row, depending on your approach). At each iteration of the exhaustive search main loop, pop one ChessBoard object from the stack and check if it’s solved. If that is the case, update the ChessPanel using updateChessBoard and then call repaint. Give a SLEEP_TIMEms pause for the user to be able to see the (new) configuration. Remember to count this new solution. If the ChessBoard object popped out from the stack is NOT solved, then try to place a new queen on different columns on the next row (or different rows on the next column, depending on your approach). Before pushing each new configuration onto the stack, make sure that this new configuration is still valid. Because if the board is already invalid, there is NO point in continuing this path. This is the pruning part of the algorithm. CAREFUL HERE: while creating new configurations, do not change and use the current configuration object. Instead, CLONE it first and then make changes on the cloned object. Otherwise, you will be making changes on the same configuration and pushing the same object onto the stack. When the stack becomes empty it means that all solutions were found. Return the number of solutions found. Submission To avoid having points deducted, you MUST submit your project using the right format, which is: a zip file named “prg_02.zip” with the following files ONLY: ChessBoard.java NQueens.java Those files should NOT be in a subfolder. This is the structure that I am expecting: prg_02.zip |___ChessBoard.java |___NQueens.java Make sure to write your name in all source files submitted. Use the provided comment sections. Rubric +65 ChessBoard +7 constructors +3 size +5 setQueen +5 hasQueen at location +5 hasQueen at row +20 isValid +5 queens +5 isSolved +10 clone +35 NQueens +10 stack initialization +5 exhaustive search main loop structure +10 exhaustive search implementation w/ prunning and backtracking +5 GUI update +5 solutions count -5 file submitted does not follow the format asked -5 comment sections of the source files do not list the name(s) of the student(s)
In this lab you are asked to create two classes. The first one is called LightBulb and models a light bulb with a brightness in lumens (an integer value). A LightBulb object can be turned ON and OFF. The second class is called DimmableLightBulb and it should be specialized from LightBulb with an added feature: a dimmer to control the percentage of lumens emitted by the light. Complete the lab by finishing an application that allows interaction with a light bulb. The LightBulb Class Define a constructor that accepts the amount of lumens. If the informed value is smaller/greater than the minimum/maximum accepted value, have it default to the minimum/maximum accepted value, respectively. A light bulb should always be created in the OFF state. Add basic getter/setter methods like: isOn, turnOn, turnOff, and getLumens. The DimmableLightBulb Class As mentioned previously, the DimmableLightBulb class should be a specialization from LightBulb with an extra feature: an integer from 0 to 100 that defines the dimmer value. Define a constructor in DimmableLightBulb that accepts the amount of lumens. Use super to call the parent’s constructor, forwarding the lumens informed value to it. Set the initial value for the dimmer to its maximum possible value. Add basic getter/setter methods like: getDimmer and setDimmer. Make sure setDimmer prevents the user to set a dimmer value that is invalid. The RoomFrame Class The RoomFrame class allows users to pick which type of light bulb to be created: the basic one or the dimmable one. Users also have the ability to choose the value for the amount of lumens.The GUI is implemented for you and it has an ON and OFF switch to control the light. If the chosen light is dimmable, the GUI will also display a slider for the dimmer. The figure below shows the GUI for the two types of light. Follow the to do’s embedded in the code to complete the lab. Hint: use the instanceof operator to determine if an object is of a particular type: LightBulb or DimmableLightBulb.The actual lumens of a dimmable light bulb is adjusted based on the dimmer (a percent from 0-100). For example, if the factory’s lumen of a dimmable light bulb is 1300 but the dimmer is set to 50, then the actual lumen displayed by the light bulb is adjusted to 50% of 1300 or 650 lumens. Rubric +1 TODO #1 (LightBulb class) +1 TODO #2 (DimmableLightBulb class) +1 TODO #3 (ON/OFF control) +1 TODO #4 (dimmer control) +1 TODO #5 (main)
