Solution Manual For Structured Computer Organization, 6th Edition

Preview (13 of 42 Pages)

100%

Solution Manual For Structured Computer Organization, 6th Edition - Page 1 preview image

Loading page ...

STRUCTUREDCOMPUTER ORGANIZATIONSIXTH EDITIONPROBLEM SOLUTIONSANDREW S. TANENBAUMVrije UniversiteitAmsterdam, The Netherlands

Solution Manual For Structured Computer Organization, 6th Edition - Page 2 preview image

Loading page ...

Solution Manual For Structured Computer Organization, 6th Edition - Page 3 preview image

Loading page ...

PROBLEM SOLUTIONS FOR CHAPTER 13SOLUTIONS TO CHAPTER 1 PROBLEMS1.a. A translator converts programs in one language to another.b. An interpreter carries out a program instruction by instruction.c. A virtual machine is a conceptual machine, one that does not exist.2.It is possible, but there are problems.One difficulty is the large amount ofcode produced.Since one ISA instruction does the work of many microin-structions, the resulting program will be much bigger. Another problem is thatthe compiler will have to deal with a more primitive output language, hence it,itself, will become more complex.Also, on many machines, the micropro-gram is in ROM. Making it user-changeable would require putting it in RAM,which is much slower than ROM. On the positive side, the resulting programmight well be much faster, since the overhead of one level of interpretationwould be eliminated.3.During the detailed design of a new computer, the device and digital logic lev-els of the new machine may well be simulated on an old machine, which putsthem around level 5 or 6.4.Each level of interpretation slows down the machine by a factor ofn/m. Thus,the execution times for levels 2, 3, and 4 arekn/m,kn2/m2, andkn3/m3, re-spectively.5.Each additional level of interpretation costs something in time.If it is notneeded, it should be avoided.6.You lose a factor ofnat each level, so instruction execution times at levels 2,3, and 4 arekn,kn2, andkn3, respectively.7.Hardware and software are functionally equivalent. Any function done by onecan, in principle, be done by the other.They are not equivalent in the sensethat to make the machine really run, the bottom level must be hardware, notsoftware. They also differ in performance.8.Not at all. If you wanted to change the program the difference engine ran, youhad to throw the whole computer out and build a new one.A modern com-puter does not have to be replaced because you want to change the program. Itcan read many programs from many CD-ROMs.9.A typical example is a program that computes the inner product of two arrays,AandB. The first two instructions might fetchA[0] andB[0], respectively. Atthe end of the iteration, these instructions could be incremented to point toA[1] andB[1], respectively. Before indexing and indirect addressing were in-vented, this was done.

Solution Manual For Structured Computer Organization, 6th Edition - Page 4 preview image

Loading page ...

4PROBLEM SOLUTIONS FOR CHAPTER 110.Raw cycle time is not the only factor. The number of bytes fetched per cycleis also a major factor, this increasing with the larger models. Memory speedand wait states play a role, as does the presence of caching. A better I/O archi-tecture causes fewer cycles to be stolen, and so on.11.The design of Fig. 1-5 does I/O one character at a time by explicit programcommand. That of of Fig. 1-6 can use DMA to have the controller do all thework, relieving the CPU of the burden, and thus making it potentially better.12.Each person consumes 730 tags per nonleap year. Multiply by 300 million andyou get 219 billion tags a year. At a penny a tag, they cost $2.19 billion dol-lars a year.With GDP exceeding $10 trillion, the tags add up to 0.02% ofGDP, not a huge obstacle.13.The following appliances are normally controlled these days by embeddedsystems: alarm-clock radios, microwave ovens, television sets, cordless tele-phones, washing machines, sewing machines, and burglar alarms.14.According to Moore’s law, next year the same chip will have 1.6 times asmany transistors. This means that the area of each transistor will be 1/1.6 or0.625 times the size of this year’s transistors.Since the area goes like thesquare of the diameter, the diameter of next year’s transistors must be 0.079microns.15.In three years the power has doubled twice so the execution time is down by afactor of four. Thus, a 4-hour run will take 1 hour then. In 6 years we gain an-other factor of four in power, so the run time then decreases to 15 min. If westart the simulation now, it will complete in 5 years, but if we start the simula-tion in 3 years it will run four times faster and thus complete in 1.25 years. Ifwe add the 3-year delay in starting plus the 1.25 year execution time, the runwill complete in 4.25 years, which is faster than starting the run now, whichwould take 5 years from the starting date to complete.16.The current numbers obviously depend on when the calculation is being made,but for example, assume the instruction execution rate is 1 billion instruc-tions/sec, the memory is 1 GB, and the cost is $500. The speed gain is 2000.The 7090 had 1,179,648 bits of memory, whereas 1 GB is 8,589,934,592 bitsgiving a memory gain of 7281.Thus, the speed-size product is 14,562,000times better. And with a price improvement of 6000, the total gain is 87.372million times better. Now let’s scale the aircraft using the same numbers. If itcould fly 2000 faster, it would go 1.18 million km/hr, which means it could cir-cle the earth in 2 min. A gain of 7281 in capacity implies about 1.3 millionpassengers. And our plane would cost about $667.17.After mainframes, we had personal computers. A current development is mov-ing computation to the cloud, which is basically centralized computing all overagain.

Solution Manual For Structured Computer Organization, 6th Edition - Page 5 preview image

Loading page ...

PROBLEM SOLUTIONS FOR CHAPTER 25SOLUTIONS TO CHAPTER 2 PROBLEMS1.The data path cycle is 20 nsec. The maximum number of data path cycles/secis thus 50 million. The best the machine could do is thus 50 MIPS.2.The program counter must be incremented to point to the next instruction. Ifthis step were omitted, the computer would execute the initial instruction for-ever.3.You cannot say anything for sure.If computer 1 has a five-stage pipeline, itcanissueupto500millioninstructions/second.Ifcomputer2isnotpipelined, it cannot do any better than 200 million instructions/sec. Thus with-out more information, you cannot say which is faster.4.On-chip memory does not affect the first three principles. Having onlyLOADsandSTOREs touch memory is no longer required. There is no particular rea-son not to have a memory-to-memory architecture if memory references are asfast as register references. Likewise, the need for many registers becomes lessin this environment.5.The monastery resembles Fig. 2-7, with one master and many slaves.6.The access time for registers is a few nanoseconds. For optical disk it is a fewhundred milliseconds. The ratio here is about 108.7.Sixty-four 6-bit numbers exist, so 4 trits are needed. In general, the number oftrits,k, needed to holdnbits is the smallest value ofksuch that 3k≥2n.8.A pixel requires 6 + 6 + 6 = 18 bits, so a single visual frame is 1. 8×107bits.With 10 frames a second, the gross data rate is 180 Mbps. Unfortunately, thebrain’s processing rate is many orders of magnitude less than this.As anexperiment, try watching the random noise on a color television for a few min-utes when no station is broadcasting and see if you can memorize the color bitpattern in the noise.9.With 44,000 samples per second of 16 bits each, we have a data rate of 704kbps.10.There are 2 bits per nucleotide, so the information capacity of the humangenome is about 6 gigabits.Dividing this number by 30,000, we get about200,000 bits per gene. Just think of a gene as a 25-KB ROM. This estimate isan upper bound, because many of the nucleotides are used for purposes otherthan coding genes.

Solution Manual For Structured Computer Organization, 6th Edition - Page 6 preview image

Loading page ...

6PROBLEM SOLUTIONS FOR CHAPTER 211.For efficiency with binary computers, it is best to have the number of cells be apowerof2.Since1,073,741,824is230,itisreasonable,whereas1,000,000,000 is not.12.From 0 to 9 the codes are: 0000000, 1101001, 0101010, 1000011, 1001100,0100101, 1100110, 0001111, 1110000, and 0011001.13.Just add a parity bit: 00000, 00011, 00101, 00110, 01001, 01010, 01100,01111, 10001, and 10010.14.If the total length is 2n−1 bits, there arencheck bits. Consequently, the per-centage of wasted bits isn/(2n−1)×100%. Numerically fornfrom 3 to 10we get: 42.9%, 26.7%, 16.1%, 9.5%, 5.5%, 3.1%, 1.8%, and 1.0%.15.Each 8-bit character is put into a 12-bit codeword where positions 1, 2, 4, and8 are check positions. After calculating the check digits and grouping eachconsecutive 4 bits into a hex digit, the 5 character ASCII string is encoded inhex as: C85 DD1 DF2 5F4 4D8.16.Each 8-bit ASCII character is encoded into three hex digits.The first set ofhex digits: 0D3, has an error in bit 12 (as indicated by the fact that bit 4 and bit8 have the wrong parity). The next set, DD3 has bit 11 wrong; the set 0F2 hasbit 7 wrong; the set 5C1 has bit 9 wrong; the set 1C5 has bit 1 wrong; the lastset CE3 does not contain any errors. After the bit positions are corrected andthe data extracted from the code words and looked up in the ASCII table, theencoded characters are: babies.17.With 4096 bits/sector and 1024 sectors/track, each track holds 4,194,304 bits.At 7200 RPM, each rotation takes 1/120 sec. In 1 sec it can read 120 tracksfor a rate of 503,316,480 bits/sec or 62,914,560 bytes/sec.18.At 160 Mbytes/sec and 4 bytes/word, the disk transfer rate is 40 millionwords/sec. Of the 200 million bus cycles/sec, the disk takes 1/5 of them. Thusthe CPU will be slowed down by 20 percent.19.Logically it does not matter, but the performance is better if you allocate fromthe outside in. One rotation of the outermost track takes as long as one rota-tion of the innermost track (because hard disks rotate with constant angularvelocity), but there are more sectors on the outermost track, so the transfer rateis higher.It is smarter to use the high-performance sectors first.Maybe thedisk will never fill up and you will never have to use the lowest-performancesectors.20.A cylinder can be read in four rotations.During the fifth rotation, a seek isdone to the next cylinder. Because the track-to-track seek time is less than therotation time, the program must wait until sector zero comes around again.Therefore, it takes five full rotations to read a cylinder and be positioned tostart reading the next one. Reading the first 9999 cylinders thus takes 49,995

Solution Manual For Structured Computer Organization, 6th Edition - Page 7 preview image

Loading page ...

PROBLEM SOLUTIONS FOR CHAPTER 27rotations.Reading the last cylinder requires four rotations, because no finalseek is needed. The 49,999 rotations at 10 msec/rotation take 499.99 sec. Ifthe sectors are skewed, however, it may be possible to avoid the fifth rotationper track.21.RAID level 2 can recover not only from crashed drives but also from undetect-ed transient errors.If one drive delivers a single bad bit, RAID level 2 willcorrect this, but RAID level 3 will not.22.In mode 2, the data streams at 175,200 bytes/sec. In a 80-min time span, thenumber of seconds is 5920, so the size of a 80-min mode-2 CD-ROM is840,960,000 bytes or 802 MB.Of course, in mode 2 there is no error cor-rection, which is fine for music but not for data. In mode 1, only 2048/2336 ofthe bits are available for data, reducing the payload to 737,280,000 bytes or703 MB.23.The mode does not matter, since the laser has to pulse for preamble bits, databits, ECC bits, and all the overhead bits as well. The gross data rate at 1x is 75sectors/sec, each sector consisting of 98×588=57, 624 bits. Thus 4,321,800bits/sec fly by the head at 1x. At 10x, this is 43,218,000 bits/sec. Thus eachpulse must last no more than 23.14 nsec (actually slightly less, since there is ablank interval between pulses).24.Each frame contains 345,600 pixels or 1,036,800 bytes of information. At 30fps, the rate per second is 31,104,000 bytes/sec. In 133 minutes this amountsto2. 482×1011bytes.Thediskcapacityis3. 5×230whichisabout3. 758×109bytes. We are off by a factor of 66, so the compression has to be66x.25.The read time is the size divided by the speed: 25×230/4. 5×106or about5965 sec. This is almost an hour and 39 minutes.26.The usual way to handle this would be to have a bank of 256 24-bit mappingregisters in the hardware. Whenever a byte was fetched from the video RAM,the 8-bit number would be used as an index into the mapping registers. Theregister selected would deliver the 24 bits to drive the display (typically 8 bitseach for the red, green, and blue electron guns).Thus indeed 224colors areavailable, but at any instant, only 256 are available. Changing colors meansreloading the mapping registers.27.For 32 intensities, we need 5 bits (since 25= 32). For each pixel we need 5×5= 25 bits. This gives 25×108bits/frame. A temporal resolution of 10 msecmeans 100 frames/sec so the bit rate is 2500×108bps.This is the same as312. 5×108bytes/sec. Using 1 GB = 109bytes, this is 312.5 GB/sec.

Solution Manual For Structured Computer Organization, 6th Edition - Page 8 preview image

Loading page ...

8PROBLEM SOLUTIONS FOR CHAPTER 228.The display must paint 1920×1080×75 pixels/sec. This is a total of 155.52megapixels. Thus the pixel time is 6.43 nsec.29.A page has 4000 characters. Each character uses 25% of 4 mm2, or 1 mm2.Thus a page has 4000 mm2of toner.With a thickness of 25 microns (0.025mm), the volume of toner on a page is 100 mm3.The capacity of the tonercartridge is 400 cm3or 400,000 mm3. A cartridge is good for 4000 pages.30.Each interval can transmit 6 bits, so the data rate is 6nbps.31.A 12-MHz cable with QAM-64 has a data rate of 72 Mbps.Withnfcom-puters sharing the bandwidth, each user gets 72/nfMbps. Thus the cable usergets better service if 72/nf> 2. An alternative way to write this isnf< 36. Inother words, if the 72-Mbps bandwidth is being shared by 36 active users, it isthe same as 2-Mbps ADSL; with fewer users, cable wins; with more users,ADSL wins.32.Each uncompressed image file is 18 million bytes. After 5x compression, it is3.6 million bytes. To write this in 2 sec requires a data rate of 1.8 MB/sec.33.The uncompressed image is 144 million bytes. The compressed image is 28.8million bytes.The number of images stored is thus 8×230/28. 8 million or298 images.34.A typical computer-science textbook has about a million characters, so it needsabout 1 MB. Ten thousand books require 1010bytes. A CD-ROM holds 700MB, so you need 15 CD-ROMs.A dual-layer, single-sided DVD holds 4.7GB, so the whole library fits on three DVDs.

Solution Manual For Structured Computer Organization, 6th Edition - Page 9 preview image

Loading page ...

PROBLEM SOLUTIONS FOR CHAPTER 39SOLUTIONS TO CHAPTER 3 PROBLEMS1.To a limited extent digital circuits are immune to noise. If a digital value isrepresented by, say +5 volts for 1 and 0 volts for 0, then a noise spike of 1 volthas no effect. But a noise spike of 3 volts could turn a 0 into a 1.2.The order ishamburger or hot dog and french frieswhich can be parsed ashamburger or (hot dog and french fries)or as(hamburger or hot dog) and french friesThe first parse leads to alternatives a and d. The second parse leads to alterna-tives e and d. Thus, a, d, and e are all possible. Choice h is ruled out on edu-cational grounds: the cook is too stupid to get the joke.3.He should point to one of the roads and ask: "If I were to ask the other gang ifthis is the road to Disneyland, what would they say?" If the answer is no, heshould take the road; if the answer is yes, he should not take it. The validity ofthis solution can easily be seen by trying all four combinations of right/wrongroad and liars/truth-tellers.4.The truth table required is as follows:PQP AND QP AND NOT Q(P AND Q) OR (P AND NOT Q)000000100010011111015.With three variables, the truth table has eight rows, so a function can be de-scribed by an 8-bit number. Thus, 256 functions exist. Withnvariables, thetruth table hask=2nrows and there are 2kfunctions.6.With three variables, the truth table has eight rows, so a function can be de-scribed by an 8-bit number. Thus, 256 functions exist. With four variables thetable has 16 rows, so a function can be described by a 16-bit number. Thus65,536 functions exist.7.Call the two variablesAandB. Connect the inputs to the firstNANDgate toAandB. Take the output and feed it into both inputs of the secondNANDgateand presto,AND.

Solution Manual For Structured Computer Organization, 6th Edition - Page 10 preview image

Loading page ...

10PROBLEM SOLUTIONS FOR CHAPTER 38.InputsD1,D2,D4, andD7are all connected to ground The other four inputsare tied toVcc.9.Input lineD0supplies the output for truth table rows 0000 and 0001.InputlineD1supplies the output for truth table rows 0010 and 0011, and so on. Foreach case, the function values for the two rows can be 00, 01, 10, and 11. Ifthey are 00, just wire the input to ground; if they are 11, just wire it toVcc. Ifthey are 01, notice that they are just the same as the fourth input variable,D,so wire it toD. If they are 10, wire it toD. The truth table values for the ex-ample, from 0000 to 1111, are 0111001110100001, so the circuit is as follows.D0VccD1D2D3D4D5D6D7ABCPD10.The encoder looks like this. Note that line 0 is not used.Low-order bitInput01High-order bit23

Solution Manual For Structured Computer Organization, 6th Edition - Page 11 preview image

Loading page ...

PROBLEM SOLUTIONS FOR CHAPTER 31111.The demultiplexer looks like this.BABABABInputABSelected byA12.It is a half adder withCas the sum andDas the carry.13.The chip needs four pins for the first operand, four pins for the second oper-and, four pins for the result, one pin for carry in, and one pin for carry out (tomake it cascadable), plus power and ground, for a total of 16 pins.14.The carry into stageican be written asCi=Pi−1+Si−1Ci−1, wherePi−1isthe product termAi−1Bi−1andSi−1is the sum termAi−1+Bi−1. This resultfollows directly from the fact that a carry is generated from a stage if both op-erands are 1, or if one operand and the carry in are both 1. For example,C0=0C1=P0+S0C0=P0C2=P1+S1C1=P1+P0S1C3=P2+S2C2=P2+P1S2+P0S1S2C4=P3+S3C3=P3+P2S3+P1S2S3+P0S1S2S3As soon as the inputs,AandB, are available, all thePandSterms can be gen-erated simultaneously in one gate delay time.Then the variousANDtermssuch asP0S1S2can be generated in a second gate delay. Finally, all the carriescan be produced in a third gate delay. Thus, all the carries are available afterthree gate delays, no matter how many stages the adder has. The price paid forthis speedup is a considerable number of additional gates, of course.15.The timing of the circuit can be found by writing a 0 on each of the input linesand then tracing them through the circuit, adding 2 at each gate. TheAinputtakes 4 nsec to become available, so the output of the logic unit takes 8 nsecand the final output for a Boolean operation takes 10 nsec. The decode linesthat drive the logic unit each have two gate delays, so the enable lines are set

Solution Manual For Structured Computer Organization, 6th Edition - Page 12 preview image

Loading page ...

12PROBLEM SOLUTIONS FOR CHAPTER 3in plenty of time.The adder also takes 6 nsec to produce its contribution tothe output gate after it hasA. Worst case through the whole circuit is 12 nsec.16.The ALU is already capable of subtraction.Note that in 2’s complement,B−A=B+(−A). To get−A, we can useA+1. Thus, to subtractAfromBwe need to addB,Aand then increment the sum. The circuit can already dothis by assertingINVAandINCand then adding the two inputs.17.A basic cycle is 11 nsec, including propagation. Sixteen cycles take 176 nsec.However, the last propagation is not needed, so the answer is available 175nsec after the start.18.One way is to negateENB, forcingBto 0, then choosing function code 01 toselectBas the ALU function. The 1’s complement of 0 is−1 in 2’s comple-ment (all 1 bits). As long asINCis negated, the control lines forAdo not mat-ter.A second way is to negate and invertA, putting all 1s on theAinput.Then negateENBto forceBto 0. WithAequal to−1 andBequal to 0, we caneither add or OR them together.19.TheNANDlatch is wired the same way as theNORlatch. Normally, both in-puts should be 1 to achieve consistency between input and output.20.Use the same circuit, but replace theANDgate in the pulse generator by aNORgate. The only time both inputs will be low is just after the falling edge.21.The design uses twoANDgates for chip enable logic plus twoANDgates perword select line plus oneANDgate per data bit.For a 256×8 memory thiscomes to 2 + 512 + 2048 = 2562ANDgates. The circuit also uses oneORgatefor each bit in the word; hence eight of them would be needed.22.It will not fly. Each of the four flip-flops needs three pins, forD,Q, andQ. Inaddition, the chip needs clock, power, and ground. Unless you plan on puttingout the world’s first 15-pin chip, you are going to have to use a 16-pin pack-age, thus wasting a pin. Thus, the design is not very efficient. Since an extrapin is available, you might as well do something with it to make the chip moreflexible. For example, you might use the sixteenth pin to reset all the FFs.23.The pins can be multiplexed in time. For example, withn/2 pins, half the bitsare presented in one cycle, and the other half in a succeeding cycle. Many dy-namic RAMs work this way. Even more extreme is to feed the address seriallyinto the chip a bit at a time using a single pin.24.A 32-bit-wide data bus means that 32 chips must be used in parallel, each chipproviding 1 bit. Thus, the smallest memory consists of 32 chips, which is 32megabits or 4 Mbytes.

Solution Manual For Structured Computer Organization, 6th Edition - Page 13 preview image

Loading page ...

PROBLEM SOLUTIONS FOR CHAPTER 31325.With a 20-nsec clock period,MREQmight be asserted as late as 13 nsec intoT1.The data are required 2 nsec before the high-to-low transition inT3, which oc-curs 10 nsec after the start of the cycle. From the midpoint ofT1to the mid-point ofT3is 40 nsec.Since the memory cannot start until 3 nsec after thetransition in the first cycle and has to be done 2 nsec before the transition inthe third cycle, in the worst case the memory has only 35 nsec to respond.26.The memory would now have 20−3−4=13 nsec to respond afterMREQandRDare asserted. There is not a lot of margin left, but if all the memory chipscan always respond in 10 nsec, the system will still work.27.In principle it could be negative, but it has to be asserted after the address isstable because on a write, the memory must not start changing the bytes ad-dressed until the address is valid. On reads it does not matter.28.In regular mode, it takes three cycles per transfer. In block mode, it takes onecycle per transfer once the transfer has started. Therefore block transfers havealmost three times as much bandwidth. The bus width does not matter, so it isstill three times more, even for 32-bit transfers.29.The CPU cannot assertMSYNuntil it has provided an address soTA1<TMSYN1,TMREQ1<TMSYN1, andTRD1<TMSYN1.The data cannot be asserted beforeMSYN, soTMSYN1<TD1andTD1<TSSYN1.OnceSSYNhas been asserted, the master can clean up, soTSSYN1<TMSYN2,TSSYN1<TRD2,TSSYN1<TMREQ2, andTSSYN1<TA2.Finally,TMSYN2<TD2andTMSYN2<TSSYN2.30.In a multicore system, the cores can share caches and primary memory easily.Having a shared memory multiprocessor makes programming many applica-tions easier. There is often also a high-bandwidth interconnection between thecores for signaling, etc.

Preview Mode

This document has 42 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

DevOps and Its Importance Study Notes

Veeam Certified Engineer VMCE-V12

Modules 1 - 3 Basic Network Connectivity and Commu

Notes CCNA

CCNA 200-301 Portable Command Guide 5th Edition 20

CCNA 200-301 Portable Command Guide 5th Edition 22

CCNA 200-301 Portable Command Guide 5th Edition 36

Foundations of Novell Networking Section 26

Modulo 7 DHCPv4

Build and troubleshooting Integration Challenge

Company

Explore

Study Tools