Final Exam Questions - Computer Organization | ENEE 350, Exams of Computer Architecture and Organization

Download Final Exam Questions - Computer Organization | ENEE 350 and more Exams Computer Architecture and Organization in PDF only on Docsity! ENEE350H Fall 2003 Final Examination Pages: 10 printed sides Name: _________________________________________ Time alloted: 2 hours Student ID: ______________________________________ Maximum score: 90 points University rules dictate strict penalties for any form of academic dishonesty. Looking sideways will be penalized to the fullest extent. Look at only your own exam at all times. There are 10 questions, some with subparts. Read them carefully to avoid throwing away points!! Write your answer in the space provided. Closed book, closed notes. Calculators okay. Partial credit rule: Must show your intermediate steps clearly for partial credit! 1. Fill in the blanks with at most three words: (1 point * 15 = 15 points) (a) Using a _______________________________ data structure for the symbol table of an assembler delivers O(1) lookup of symbol names. (b) One advantage of using procedures instead of macros for repeated code sequences is lower ________________________. (c) __________________________ variables are not allocated as part of the assembly code; instead they are allocated at runtime from a free list, and referenced through pointer variables. (d) The ___________________________ is a piece of software that resolves symbol declarations external to files by finding them in other files and generating correct addresses. (e) _______________________________ are a commonly used hardware-supported mechanism for ensuring race-free programs. (f) One advantage of ____________________________ allocation of file sectors on a disk is that a file’s location is completely specified by its starting sector and size alone. (g) A sequence of unused sectors on a disk is called a _______________________________. (h) Files are an abstraction provided by the ______________________________ (compiler/hardware/operating system/linker) in modern computers. (i) When segmentation and paging are combined, the number of page tables is equal to the number of ____________________________. (j) __________________________ is the name of a technique to reduce external fragmentation in segmentation by copying segments to be next to each other, thus combining free areas into one. (k) Protection among processes at the main memory level is usually provided by the operating system mechanism of _____________________________. (l) If a TLB stores page table entries from multiple processes then it is indexed by both the VPN and the ____________________________. (m) When the _____________________________ of a process does not fit in main memory, thrashing is observed. 1 (n) When an interrupt arrives, the task of looking up the table of interrupt handler addresses is done by ______________________________ (hardware/software). (o) When an exceptional event occurs at the same instruction every time the program is executed it is called a ______________________________. 2. For each subpart (i) to (xii) below, circle all correct answers from among the four given - note that more than one answer may be correct! (2 points * 12 = 24 points) (i) Register usage conventions (a) make separate compilation of different files from the same program possible. (b) are needed to correctly save and restore registers upon an interrupt. (c) may decrease register availability for program variables in some cases when compared to not using register conventions. (d) need to be known to high-level language programmers. (ii) The first pass of the assembler (a) stores declared macros in the macro table. (b) expands uses of macros. (c) computes the address of every symbol definition. (d) computes the address of every symbol reference. (iii) Uses of assembler directives often include (a) declaring global variables. (b) declaring stack variables. (c) specifying the alignment of variables. (d) specifying the addressing mode of certain instructions. 2 (xii) Usually, single-precision floating point registers (a) are distinguished from general-purpose registers in instruction formats only by using different instruction opcodes for floating-point instructions. (b) take longer to access than general-purpose registers. (c) contain unusable (wasted) bits when compared to double-precision floating-point registers. (d) are accessed in the decode stage of a DLX pipeline. 3. Consider the following code sequence running on a 5-stage DLX pipeline: (2 points * 3 = 6 points) SW 6(R5), R4 LW R1, 3(R2) (i) Is it possible for the two instructions to ever have a dependence? Is yes, under what condition? (ii) Assume that the latency of the data cache is one cycle to complete a memory operation. Will the above code execute correctly without stalling if the data cache is implemented as a simple memory bank with no extra logic? If no, then what is the functionality of extra logic that would enable stall-free execution? (1-2 sentences)? Assume cache hits. (iii) Same question as (ii) above, but with a two-cycle data cache latency: 5 4. A 32-bit byte-addressed DLX processor has a physically addressed direct-mapped data cache of size 16Kbytes and cache lines of size 16 bytes. It also implements paging with a page size of 4Kbytes. Assume the bit positions in memory addresses are numbered 0 (least significant) to 31 (most significant). (2 + 2 + 2 + 3 = 9 points) (a) What range of address bits is used as the index into the cache? (b) Can the cache be accessed in parallel with the TLB? If not, give the correct order of access. (c) Repeat part (b), but assuming a page size of 16 Kbytes. (d) Suppose we want a cache in which lines from more than one process can co-exist at the same time. Does the cache tag need to include the process ID # in addition to the high-order bits of the address? Give a reason. (1-2 sentences) [Hint: Page size does not affect the answer here.] 6 5. Consider a linked list task_list of type struct task containing descriptors of to-be-done tasks: struct task{ . . . struct task *next; }; struct task *task_list; struct task *my_task; Two processes P0 and P1 running on different processors both execute the following code to process tasks one-by-one from task_list.which is shared among the processes. The my_task variable is private to each process. The intended behavior is that each task is processed by exactly one process and all tasks are eventually completed. Unfortunately the following code is wrong. while (task_list != NULL) { \\S1 my_task = task_list; \\S2 task_list = task_list -> next; \\S3 process_task (my_task); \\S4 } (2 + 2 + 5 = 9 points) (a) Describe a scenario in which execution is incorrect because the same task is processed twice. (b) Can the same task be processed twice if P0 and P1 are executed on the same processor instead, inside a time-sharing operating system? If yes, describe a scenario. (c) Write a correct version of the above program using up and down semaphores on a single integer sem assumed initialized to 1. The code should allow parallel execution of process_task in a two- processor environment. Use a private integer Boolean variable done, assumed initialized to 0, which is set to 1 when task_list is empty. [Hint: Access shared variables in critical sections only!] 7