|
|
|
|
|
|
|
|
Chapter 1
No. 5. You lose
a factor at each level, so instruction execution times at level 2, 3, and
4 are kn, kn2, and kn3, respectively.
No. 6. Each level
of interpretation slows down the machine by a factor of n/m. Thus
the execution times for levels 2, 3, and 4 are kn/m, kn2/m2,
and kn3/m3 respectively.
Chapter 2
No. 14. From 0 to 9, the codes
are: 0000000, 1101001, 0101010, 1000011, 1001100, 0100101, 1100110,
0001111, 1110000, and 0011001.
No. 15. Just add a parity
bit: 00000, 00011, 00101, 00110, 01001, 01010, 01100, 01111, 10001,
and 10010.
No. 34. It says: I
LOVE YOU
No. 1.
The order is
hamburger or hot dog and french fries
which can be phrased as
hamburger or (hot dog and french fries)
or as
(hamburger or hot dog) and french fries.
No. 2. He should
point to one of the roads and ask: "If I were to ask the other gang
if this is the road to Disneyland, what would they say?" If the answer
is no, he should take the road; if the answer is yes, he should not take
it.
No. 3. With three
variables, the truth table has eight rows, so a function can be described
by an 8-bit number. Thus 28 = 256 functions exist.
with n variables, the truth table has k = 2n rows and
there are 2k functions
No. 4.
The truth table required is as follows"
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
No. 5. Call the
two variables A and B. Connect the inputs to the first NAND gate.
Feed both outputs to the second NAND gate.
No. 6. Using
the AND form of de Morgan's law:
Not (A AND (Not B)) = NOT A OR NOT (NOT B) = NOT A OR B
No. 7. Inputs
D1, D2, D4, and D7 are all
connected to Vcc. The other four inputs are grounded.
No. 8. Input
line D0 supplies the output for truth table rows 0000 and 0001.
Input line D1 for rows 0010 and 0011, and so on. For each
case, the function values for the two rows can be 00, 01, 10, and 11.
If they are 00, wire input to ground, if 11, to Vcc. If
they are 01, notice they are same as fourth input variable, D, so it is
wired to D. If 10, wire it to NOT D. The truth table values
from 0000 to 1111 are 0111001110100001.
No. 12. It is a half adder
with C as the sum and D as the carry.
No. 22. The design uses two
AND gates for chip enable logic plus two AND gates per word select line
plus one AND gate per data bit. For a 256 X 8 memory this comes to
2 + 512 + 2048 = 2562 AND gates. The circuit also uses one OR gate
for each bit in the word; hence eight OR gates would be needed.
No. 25. With a 40-nsec clock
period MREQ might be asserted as late as 28 nsec into T1.
The data are required 5 nsec before the high-to-low transition in T3,
which occurs 100 nsec after the start of the cycle. Since 100 - 28
= 72, in the worst case the memory would only have 72 nsec in which to
respond.
No. 26. The memory would
now have 62.5 - 16 - 5 = 41.5 nsec. If all memory chips can respond
in 40 nsec, the system will work.
No. 35. The average access
time is 0.2 x 5 + 0.6 x 10 + (1 - 0.2 - 0.6) x 50 = 17 nsec.
No. 1. In the
figure, A and B are ORed together, with B both enabled. (1 OR 0 =
1). Another way is to add them. Set F0 to 1.(1 +
1 = 10 that is A and 0 = A)
No. 6. All compilers
will add
BIPUSH 0
ISTORE i
at label L2. However the compiler will notice that i is not used after the if statement. Therefore the fourth and fifth instructions (ISTORE and ILOAD) are not needed. The code becomes
ILOAD j
ILOAD k
IADD
BIPUSH 3
IF_ICMPEQ L1
ILOAD j
BIPUSH 1
ISUB
ISTORE j
GOTO L2
L1: BIPUSH 0
ISTORE k
L2: BIPUSH 0
ISTORE i
No. 7.
ILOAD j
ILOAD j
ILOAD k
ILOAD k
IADD
BIPUSH 4
BIPUSH 4
IADD
IADD
IADD
ISTORE i
ISTORE i
(j + k) + 4
j + (k + 4)
No. 8. i = (j - k - 6) + (j - k - 6)
No. 11.
The code and the number of microinstructions for each one is:
ILOAD 7
ILOAD 7
IADD 5
ISTORE 8
TOTAL 27 microinstructions. At 200 MHz, each
microinstruction takes 5 nsec. 27 x 5 = 135 nsec.
No. 26.
The mean access time is 0.8 x 5 + 0.15 x (5 + 15) + 0.05 x (5 + 15 + 20)
= 4 + 3 + 4 = 11 nsec.
No. 29.
A conditional branch ties up the fetch unit for 4 cycles - one fetch and
3 dead cycles after it. The mean number of cycles spent using the
fetch unit is (1 - 0.2) x 1 + 0.2 x 4 = 0.8 + 0.8 = 1.6 fetch cycles/instruction.
Without this problem it would have been 1.0 fetch cycles per instruction.
Additional time is 1.6 - 1.0 = 0.6 or 60% more time, and the efficiency
is 1/1.6 = 0.625 or 5/8 or 62.5% .
No. 30. Prefetching will
be on the right track if all four branches are correctly predicted.
The chance is 0.94 = 0.6561
No. 5. The instructions
load 20, 40, 60, 30, 50, and 70, respectively.
No. 9. The reverse
Polish formulae are:
a. AB +
C + D + E +
b. AB
+ CD + X E +
c. AB
X CD X + E +
d. AB
- CDE X - F / G / X H X
No. 10. The corresponding infix formulae are:
a. (A +
B + C) X D
b. (A
/ B) + (C / D)
c. A /
(B X C X (D + E))
d. A +
(B X ((C + (D X E) / F) - G) / H)
No. 11. Converting to infix:
a. (A +
B) + C equals A + (B + C)
b. (A
- B) - C does not equal A - (B - C)
c. (A
X B) + C does not equal A X (B + C)
No. 12. All cases where the number of variables is not one more than the number of operators.
No. 13. The reverse Polish formulae are:
a. A B
AND C OR
b. A B
OR A B OR AND
c. A B
AND C D AND OR
No. 14. The reverse Polish formula is 2 3 X 4 + 4 2 / 1 + -. Step by step evaluation:
2 3 X 4 + 4 2 / 1 + -
6 4 + 4 2 / 1 + -
10 4 2 / 1 + -
10 2 1 + -
10 3 -
7
The generated code is:
BIPUSH 2
BIPUSH 3
IMUL
BIPUSH 4
IADD
BIPUSH 4
BIPUSH 2
IDIV
BIPUSH 1
IADD
ISUB
No. 23. The five numbers are:
a. 0000
1001 0101 1100
b. 1111
1001 0101 1100
c. 0101
1100 0011 0000
d. 0101
1100 0011 1001
e. 0011
1001 0101 1100
No. 24. By generating zero and storing it, subtracting a number from itself, and by EXCLUSIVE ORing a number with itself.
No. 25. 1101 0000 0010 1101
No. 26. B := A XOR B
A := A XOR B
B := A XOR B
No. 30. For 64 disks, we need 264 - 1 moves. At 1 minute per move that is 264 - 1 minutes or 1.84 x 1019 minutes, or 3.07 x 1017 hours, or 1.28 x 1016 days or 3.51 x 1013 years or 35.1 trillion years. So do not worry!
No. 2. The address space is 232 bytes. Each page is 8 kilobytes or 8192 bytes. The number of pages is 232/8192 =524,288 pages (219 pages).
No. 3. a.
These addresses cause faults: 2048 to 4095, 5120 to 6143, 7168 to 8191.
b. 3072, fault, 4095, 1024, 1025, fault, 2048.
No. 4. With LRU, memory looks
like this (* indicates a page fault):
, , , 0 *
, , 0, 7 *
, 0, 7, 2 *
, 0, 2, 7
0, 2, 7, 5 *
2, 7, 5, 8 *
7, 5, 8, 9 *
5, 8, 9, 2 *
8, 9, 2, 4 *
With FIFO, memory looks like this (* indicates a page fault):
, , , 0 *
, , 0, 7 *
, 0, 7, 2 *
, 0, 7, 2
0, 7, 2, 5 *
7, 2, 5, 8 *
2, 5, 8, 9 *
2, 5, 8, 9
5, 8, 9, 4 *
No. 8. (1)
6145 (2) 10 (3) page fault
(4) protection fault (5) 2050
(6) 28686 (7) 16484
(8) page fault (9) segment fault
(10) protection fault.
No. 15. LRU is better.
If a store has not sold an item for a long time, it should be dropped.
FIFO is worse as the oldest product would be a staple such as flour, salt,
sugar, coffee, etc.
No. 23. S = Sleeping,
R = Running
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
No. 26.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
No. 1. a.
Programming = 100 months, execution time = T
b. Programming = 1000 months, execution time = 0.25T
c. Programming = 100 + 10 = 110 months, execution time
= 5T/8
No. 5. No.
On pass one D is defined; on pass two C is defined; on pass three B is
defined; on Pass four A is defined.
No. 9. EVEREST = 1000,
K2 = 1001, WHITNEY = 1002, MCKINLEY = 1004, FUJI = 1007, and KIBO = 1008
No. 11. If we number the
cities 1 through 12, the first probe is number 6, New Haven. Berkeley
< New Haven, so the new list is searched from 1 through 5. The
next probe is No. 3 Cambridge. Berkeley < Cambridge, so the new
list is 1 through 2. The third probe is number 1 Ann Arbor.
Berkeley > Ann Arbor, so the list starts and ends at number 2. Berkeley.
We find it on the fourth probe.
No. 12. Yes.
No. 13. ELS = (5 + 12 + 19)
mod 19 = 17
JAN = (10 + 1 + 14) mod 19 = 6
JELLE = (10 + 5 + 12 + 12 + 5) mod 19 = 6
MAAIKE = (13 + 1 + 1 + 9 + 11 + 5) mod 19 = 2
JAN and JELLE hash to the same value, 6.
No. 21. It will need three passes: one to collect the macro definitions, one to expand the macros and build the symbol table, and one to generate the code.
No. 23. The constants are 0, 200, 1000, 1600, and 2100, respectively.
No. 1. It is MIMD. The
general work is the same, but each bee looks for its own flowers (its own
instruction steam). There is no lockstep coordination.
No. 2. (a) 2
(b) 1 (c) 6 (d) 4
(e) 6 (f) 4 (g) 3
(h) 4
No. 3 (a) 0
(b) 6 (c) 0 (d) 1
(e) 1 (f) 3 (g) 2
(h) 3
No. 6. The routes are:
1, 2, 3, 4, 8, 12
1, 2, 3, 7, 8, 12
1, 2, 3, 7, 11, 12
1, 2, 6, 7, 8, 12
1, 2, 6, 10, 11, 12
1, 5, 6, 7, 8, 12
1, 5, 6, 7, 11, 12
1, 5, 6, 10, 11, 12
1, 5, 9, 10, 11, 12
No. 7. It can
be done in four register as follows:
Register 1: A, E, F
Register 2: B, G
Register 3: I, J, C, L
Register 4: H, K, D
No. 8. It is
live in 4 - 7, 9 - 12, and 15 - 17.
No. 11. During the first
three cycles there is no output. Thereafter, one element pops out
every cycle, so it takes 3 + 1024 = 1027 cycles or 1027 nsec.
No. 12. The bus arbitrator
decides who goes first. Then there is sequential access.
No. 17. a.
The probability that any machine is silent is 1 - p, so the probability
hat all n are silent is (1 - p)n
b. The probability that machine 0 is the only
requester is (1 - p)n - 1. Since all n machines are equally
likely to transmit, the probability that any of them does is np(1 - p)n
- 1.
c. The probability of two or more is just 1 minus the
above two expressions or - (1 - p)n - 1 - (1 - p)n.
No. 20. CPUs 000, 010, 100, and 110 are cut off from memories 010 and 011.
No. 1 The numbers
are 11111000000, 111110100000, and 10000000000000, respectively.
No. 2. In decimal
it is 617, in octal 1151, and in hex 269.
No. 3. All valid
except BAG
No. 4. The answers:
1100100, 10201, 1210, 400, 244, 202, 144, and 121.
No. 5. rk.
No. 6. With just
hands (10 bits), you can count to 1023. With hands and feet the limit
becomes 220 - 1 = 1,048,575. In two's complement the range
is -542,288 to +524,287.
No. 7. The results
are: 10011100, 11111110, and 00000000. The first calculation results
in an overflow. The subtractions are done by forming the two's complement
of the subtrahend and then adding to the minuend.
No. 8. The results
are: 10011100, 11111110, 00000000, and 11111111. The first
calculation gives an overflow. The subtraction is done by forming
the one's complement of the subtrahend and adding o the minuend.
No. 9. The five
sums are : 001, 11, 101, 011, and 000, respectively. The NZV condition
code bits are 000, 100, 100, 000, and 011, respectively.
No. 10. The numbers are:
006, 997, 100, 985, 998, and 000.
No. 11. The rules for addition
of nine's complement is analogous to that for the addition of one's complement
numbers; the carry is added to the number. The sums are: 0001,
9999, 9994, and 0044.
No. 12. Similar to two's
complement. Add and ignore the carry.
No. 14. 10101 (7 X
3 = 21)