Questions and Answers of Principles Algorithms And Systems

1. Under what circumstances will a string of an arbitrary number of inverters with a feedback loop, as in Figure 11.1, produce a stable network?
2. Construct tables analogous to Figures 11.3 and 11.4 to show that changing R to 1 and back to 0 resets the SR latch to Q = 0 if it starts in state Q = 1.
3. Define the following points in Figure 11.10: (1) A is the output of the top master AND gate.(2) B is the output of the bottom master AND gate. (3) C is the output of the inverter. (4) D is the
4. Do Exercise 3 with SR = 01 and Q = 1 before the arrival of the clock pulse.
5. Draw the state transition diagram, as in Figure 11.14, for the following flip-flops:(a) JK*(b) D(c) T
6. Draw the timing diagram of Figure 11.21(c) for the toggle flip-flop with the D input replaced by T.
7. Construct the T flip-flop from an SR flip-flop.
8. This section shows how the JK and D flip-flops can be constructed from the SR flip-flop and a few gates. In fact, any flip-flop can be constructed from any other with the help of a few gates.
9. Modify Figure 11.10, the implementation of the SR master–slave flipflop, to provide asynchronous preset and clear inputs, as in Figure 11.32. When preset and clear are both 0, the device should
10. Draw the logic diagram and the state transition diagram for a sequential circuit with two JK flip-flops, FFA and FFB, and two inputs, X1 and X2, with flip-flop inputs JA = X1 B JB = X1 A¯KA = X2
11. Draw the logic diagram and the state transition diagram for a sequential circuit with one JK flip-flop, FFA; one T flip-flop, FFB; and one input, X, with flip-flop inputs J = X ⊕ B T = X ⊕ A
12. Draw the logic diagram and the state transition diagram for a sequential circuit with two SR flip-flops, FFA and FFB; two inputs, X1 and X2, with flip-flop inputs SA = X1 SB = X1¯ X2¯ A¯RA =
13. Design the sequential circuit of Figure 11.33 using the following flip-flops:*(a) D(b) T
14. FIGURE 11.54 is a state transition diagram for a sequential circuit with three flip-flops and one input. It counts up in binary when the input is 1 and remains in the same state when the input is
15. FIGURE 11.55 is a state transition diagram for a sequential circuit with three flip-flops and one input. It counts up in binary when the input is 1 and counts down when the input is 0.Design the
16. FIGURE 11.56 is a state transition diagram for a sequential circuit with two flip-flops and two inputs. It counts up in binary when the input is 01, counts down in binary when the input is 10,
17. FIGURE 11.57 is a state transition diagram for a sequential circuit with three flip-flops and one input. It is a three-bit shift right register. If the input is 0, a 0 is shifted into the most
18. A sequential circuit has six state registers and three input lines. (a) How many states does it have? (b) How many transitions from each state does it have? (c) How many total transitions does it
19. (a) How many AND gates, OR gates, and inverters are in the memory chip of Figure 11.42?Include the gates in the decoder but not in the D flip-flops. (b) How many of each element are in the memory
20. In practice, the chip select line of a memory chip is asserted low, and the line is labeled CS¯instead of CS to indicate that fact. How would Figure 11.49 change if the chip select lines on all
21. A computer system has a 16-bit wide data bus. (a) If you have a box of 1 Ki × 1 dynamic RAM chips, what is the smallest number of bytes of memory this computer can have? (b)Answer part (a) if
22. You have a small CPU with a 10-bit address bus. You need to connect a 64-byte PROM, a 32-byte RAM, and a 4-port I/O chip with two address lines. Chip selects on all chips are asserted high. (a)
23. Show how the individual multiplexers in the top port of Figure 11.53 are connected. You may use ellipses (. . .).
24. How many AND gates, OR gates, and inverters are in the two-port register bank of Figure 11.53? Include the gates necessary to construct the decoder and the multiplexers, but not the ones in the D
22. For Figure 12.45(b), place a checkmark for each circuit that is idle in each of the cycles in the table below, and list the total number of circuits that are idle for each cycle. Cycle 7 8 9 10
37. Insert the .ALIGN dot command and the NOP0 instruction to align the following Pep/9 assembly language programs for the Pep/9 processor with the two-byte data bus. Remember that all CALL
36. Write the control sequence with the two-byte data bus to implement the ISA3 instructions of Problem 33. Assume that all addresses and word operands are aligned at even addresses.Compare the
35. Write the control sequence with the two-byte data bus to implement the ISA3 instructions of Problem 32. Assume that all addresses and word operands are aligned at even addresses.Compare the
34. Write the control sequence with the two-byte data bus for the von Neumann cycle to fetch the operand specifier and increment PC accordingly. (a) Assume the program counter is even so that the
33. Write the control sequence with the one-byte data bus to implement the following flow of control ISA3 instructions. Assume that the instruction has been fetched and the program counter has been
32. Write the control sequence with the one-byte data bus to implement the following nonunary ISA3 instructions. Assume that the instruction has been fetched and the program counter has been
31. Write the control sequence with the one-byte data bus to implement the following nonunary ISA3 instructions. Assume that the instruction has been fetched and the program counter has been
30. Write the control sequence with the one-byte data bus to implement the ASLA instruction, which does an arithmetic shift left of the accumulator and puts the result back in the accumulator. The
29. Write the control sequence with the one-byte data bus to implement the following unary ISA3 instructions. Assume the instruction has been fetched and the program counter has been incremented.(a)
28. Write the control sequence with the one-byte data bus for the von Neumann cycle to fetch the operand specifier and increment PC accordingly. Assume the instruction specifier has been fetched and
27. The finite-state machine of Figure 12.48 for branch prediction moves from predicting no branch to predicting branch only if two consecutive branches were made (and similarly for moving from
26. Construct the one-input finite-state machine of Figure 12.48 to implement two-bit dynamic branch prediction. Minimize your circuit with a Karnaugh map. (a) Use two SR flip-flops.(b) Use two JK
25. (a) In Figure 12.47 for one-bit dynamic branch prediction, what pattern of Taken outcomes will produce the maximum percentage of incorrect predictions? What is the maximum percentage? (b) In
24. The text states that you can eliminate the write-back stage of an unconditional branch under the assumption that the next instruction has been delayed. (a) Draw cycles 7 through 16 of Figure
23. Suppose the five-stage pipeline of Figure 12.45(a) executes a branch 15% of the time, each branch causing the next instruction that executes to stall until the completion of the branch, as in
21. In Figure 12.43, (a) how many bits are in each of the two IF/ID boundary registers? (b) How many bits are in each of the four ID/Ex boundary registers? (c) How many bits are in each of the three
20. (a) What is the RTL specification for the lw instruction? (b) For Figure 12.40, write the control signals to execute the lw instruction.
19. (a) Suppose a C compiler for the MIPS machine associates $s5 with variable g. How does it translate g = 529371;into MIPS assembly language? (b) Write the machine language translation of the
18. (a) Write the MIPS assembly language statement to allocate 12 bytes of storage on the runtime stack. (b) Write the machine language translation of the instruction in part (a).
17. (a) Suppose a C compiler for the MIPS machine associates $s5 with array a and $s6 with variable i. How does it translate a[i] = a[i+1];into MIPS assembly language? (b) Write the machine language
16. (a) Suppose a C compiler for the MIPS machine associates $s4 with variable g, $s5 with arraya, and $s6 with variable i. How does it translate g = a[i+3];into MIPS assembly language? (b) Write the
15. (a) Suppose a C compiler for the MIPS machine associates $s4 with variable g, $s5 with arraya, and $s6 with variable i. How does it translate a[i] = g;into MIPS assembly language? (b) Write the
14. (a) Suppose a C compiler for the MIPS machine associates $s4 with variable g, $s5 with arraya, and $s6 with variable i. How does it translate g = a[i];into MIPS assembly language? (b) Write the
13. (a) Write the MIPS assembly language statement to shift the content of register $s2 nine bits to the left and put the result in $t5. (b) Write the machine language translation of the instruction
12. (a) Suppose a C compiler for the MIPS machine associates $s4 with arraya, $s5 with variable g, and $s6 with arrayb. How does it translate a[4] = g + b[5];into MIPS assembly language? (b) Write
11. Suppose a CPU can address 1 MByte of main memory. It has a fully associative cache (see Exercise 10) with 16 32-byte cache lines. (a) How many bits are required for a memory address? (b) How many
10. A direct-mapped cache is at one extreme of cache designs, with set-associative caches in the middle. At the opposite extreme is the fully associative cache, where there is in essence only one
9. For Figure 12.30, (a) draw the implementation of a comparator, the circle with the equals sign. (Hint: Consider the truth table of an XOR followed by an inverter, sometimes called an XNOR gate.)
8. If the CPU of Exercise 7 had a two-way set-associative cache, again with 256 eight-byte cache lines, how many bits would be required for each cache entry?
7. A CPU can address 16 MiB of main memory. It has a direct-mapped cache in which it stores 256 eight-byte cache lines. (a) How many bits are required for a memory address? (b) How many bits are
6. The CPU requests the byte at address 4675 (dec) with the cache of Figure 12.28. (a) What are the nine bits of the Tag field? (b) What are the four bits of the Byte field? (c) Which cell of the
5. The text predicts that we will never need to transition from 64-bit computers to 128-bit computers because we will never need main memories bigger than 16 billion GiB. Silicon crystals have a
4. Figure 12.7 combines cycle 6 with cycle 2 and cycle 7 with cycle 3 in Figure 12.5 to speed up the von Neumann cycle. Can you combine cycle 6 with cycle 4 and cycle 7 with cycle 5 instead? Explain.
3. Figure 12.7 combines cycle 6 with cycle 2 and cycle 7 with cycle 3 in Figure 12.5 to speed up the von Neumann cycle. Can you combine cycle 6 with cycle 3 and cycle 7 with cycle 4 instead? Explain.
2. Design the three-input, one-output combinational circuit AndZ of Figure 12.2. (a) Minimize the AND-OR circuit with a Karnaugh map. (b) Minimize the OR-AND circuit with a Karnaugh map. (c) Which
1. Draw the individual lines of the eight-bit bus between MDR and the main memory bus. Show the tri-state buffers and the connection to the MemWrite line.
9. For the grammar of Figure 7.8, draw the syntax tree for from the following string, assuming that alpha, beta, gamma, and main are valid s and C1, S1, and S2 ares:int main(){ int gamma;alpha
10. The question this exercise poses is “Can two different grammars produce the same language?” The grammars in FIGURE 7.49 and FIGURE 7.50 are not the same because they have different
13. Draw a deterministic FSM that recognizes strings of 1’s and 0’s specified by each of the following criteria. Each FSM should reject any characters that are not 0 or 1. *(a) The string of
19. Write an assembler for Pep/9 assembly language. Complete the following milestones in the order they are listed.(a) Write class Tokenizer with method getToken(), to implement the FSM of FIGURE
1. What are the two purposes of an operating system?
2. The loader in Figure 8.3 executes with the following input:12 00 05 00 00 31 00 03 39 00 03 D0 00 0A F1 FC 16 49 00 15 00 54 68 61 74 27 73 20 61 6C 6C 2E 0A 00 zz Assume that the loop from FC1A
3. Do Exercise 2 for the 32nd execution of the loop.
4. The program of FIGURE 8.34 executes, generating an interrupt for DECI. For Figure 8.6, the entry to and exit from the trap handler, state the values in the following registers as four hexadecimal
5. Do Exercise 4 for the DECO instruction. FIGURE 8.34 The program for Exercise 4. 0000 120005 BR main 0003 0000 num: .BLOCK 2 0005 310003 main: DECI num, d 0008 390003 DECO num, d ; Branch around
6. Do Exercise 4 for the STRO instruction.
7. The program in Exercise 4 runs with an input of 37. For Figure 8.14, the DECI trap handler, state the values in registers a–h as four hexadecimal digits and answer the question in (i):*(a) A
8. Do Exercise 7 with an input of -295.
9. The program in Exercise 4 runs with an input of 37. For Figure 8.15, the DECO trap handler, state the values in the following registers as four hexadecimal digits:*(a) A after LDWA at FEFA*(b) A
10. Do Exercise 9 with an input of -2068.
11. The program in Exercise 4 runs and executes the STRO instruction. For Figure 8.16, the STRO trap handler, state the values in the registers in hexadecimal:(a) A after LDWA at FFCE(b) A〈8..15〉
12. The DECI instruction with direct addressing at 0005 in Figure 5.11 executes, generating a trap. The trap handler calls the setAddr routine in Figure 8.10. State the values in the index register
13. The DECO instruction with indirect addressing at 004B in Figure 6.41 executes, generating a trap. The trap handler calls the setAddr routine in Figure 8.10. State the values in the index register
14. The DECI instruction with stack-relative addressing at 0009 in Figure 6.4 executes, generating a trap. The trap handler calls the setAddr routine in Figure 8.10. State the values in the index
15. The DECI instruction with stack-indexed addressing at 0013 in Figure 6.36 executes for the second time, generating a trap. The trap handler calls the setAddr routine in Figure 8.10. State the
16. The DECI instruction with stack-deferred indexed addressing at 0016 in Figure 6.38 executes for the second time, generating a trap. The trap handler calls the setAddr routine in Figure 8.10.
17. A short notation for the interleaved execution sequence in Figure 8.23 is 112221, which represents statements executed by P1, P1, P2, P2, P2, P1 in Figure 8.22. (a) How many different execution
18. The following attempt to implement critical sections is similar to the program in Figure 8.26 except for the order of the statements in the entry section:*(a) Does the algorithm guarantee mutual
19. Show from the definitions of wait() and signal() that the magnitude of s is the number of processes blocked.
20. Let I represent an execution of init(s), W of wait(s), and S of signal(s). Then, for example, IWWS represents the sequence of calls init(s), wait(s), wait(s), and signal(s) by some processes in
21. Suppose three concurrent processes execute the following code:Explain how the code guarantees mutual exclusion of all three critical sections. Process P1 do wait (mutEx); critical section signal
22. Suppose s and t are two semaphores initialized with init(s) and init(t). Consider the following code fragment of two concurrent processes:*(a) Does the algorithm guarantee mutual exclusion? If
23. Consider the code fragment of two concurrent processes:Modify the code fragment to guarantee that Statement 5 occurs before Statement 2. Use a semaphore. Process P1 Process P2 Statement 1
24. Each of the following code fragments contains a bug in the entry or exit section. For each fragment, state whether mutual exclusion still holds. If it doesn’t, show an execution sequence that
25. An operating system has processes P1, P2, P3, and P4 and resources R1 (one resource), R2(one resource), R3 (two resources), and R4 (three resources). The notation (1, 1), (2, 2), (1, 2) means
26. Implement a new unary instruction in place of NOP0 called ASL2 that does two left shifts on the accumulator. NZC should should correlate with the new value in the accumulator from the second
27. Implement a new nonunary instruction in place of NOP called ASLMANY whose operand is the number of times the accumulator is shifted left. Allow only direct addressing. NZC should correlate with
28. Implement a new nonunary instruction in place of NOP called MULA that multiplies the operand by the accumulator and puts the result in the accumulator. Allow only direct addressing. Use the
29. Direct addressing is immediate addressing deferred. Indirect addressing is direct addressing deferred. You can carry this concept one level further with double indirect addressing, which is
30. Implement a new nonunary instruction in place of NOP called BOOLO, which means Boolean output. It should output false if the operand is zero and true otherwise. Allow immediate, direct, and
31. Implement a new unary instruction in place of NOP0 called STKADD. It should replace the two topmost items on the stack with their sum. Set NZVC according to the results of the addition.Use the
32. Implement a new nonunary instruction in place of NOP called XORA, which computes the bitwise exclusive OR operation with the operand and the accumulator, placing the result in the accumulator.
33. This problem is to implement new nonunary instructions to process floating point numbers.Assume that floating point numbers are stored with all the special values of IEEE 754 but with a two-byte
1. Using the format of Figure 9.4, devise a job execution sequence for which the first-fit algorithm would require compaction before the best-fit algorithm. Sketch the fragmentation in main memory
2. Figure 9.10 shows how a page table in a paging system performs the same transformation of the logical address as the base register does in a multiprogramming system. The equivalent job of the

Showing 1 - 100 of 532