A) Suppose we have a computer with 64 registers and 10 gigabytes of memory, and

Question

A) Suppose we have a computer with 64 registers and 10 gigabytes of memory, and we want to support 100 different opcodes. How long do the instructions need to be for each of the following? Register-to-register instructions, register-to-storage instructions, and storage-to-storage instructions? Then assuming we need to round lengths to the next largest power of 2, what would the lengths be? On a machine with 32-bit words, how many words do we need for each type of instruction?

B) Suppose we want to sort in alphabetical order a large list of names. Suppose we have a multicore machine with eight processors, sharing a single memory. Assume sorting requires time of 10*N*log2(N) where N is the number of items to sort and log2 means the logarithm to base 2. Then when sorting is done on separate processors the items must be merged, which you should assume requires time (N1+N2) where N1 is the number of items in the first set and N2 is the number of items in the second. What speedup to we get when we split the processing as evenly as possible over eight processors compared to doing all the processing on one processor? Give the answer as an algebraic formula. Then compute the speedup for the specific number of 1,048,576 items. Show your math and explain your assumptions about hoe the sorting and merging is implemented.

C) Suppose we have a hard disk that rotates as a fixed rate and has six tracks, each of the same width, with 10 blocks per track. Suppose the rotation speed of the disk is TR and the time for the disk head to move from one track to its neighbor is TS (and also from starting position to the outermost track). Suppose the disk head starts at the outmost position.

i. How much time is necessary to read the entire contents of the disk?

ii. How much time on the average is necessary to read one randomly chosen block on each track, whose block number is randomly chosen in advance?

Explanation / Answer

A).
We will go by each of the information and its effect on the instruction size.
A general instruction has three parts namely: opcode, source, destination. A instruction must have sufficient bits for accomodating all of these.
Given there are 100 opcodes, thus, no.of bits needed for representing 100 opcodes are log(100) (for base 2).
Let l1 be length of opcode , l2 the source and l3 the destination in the instruction.
Thus, for all the cases l1 = log(100) = 6.64 = 7 bits. (we should take the upper bound)

a) register to register
l2 and l3 are length of bits for registers.
Given there are 64 registers. Bits needed for registers,
l2,l3 = log(64) = 6
Thus, length of instruction, la = l1+l2+l3 = 7+6+6 = 19 bits.

b) register to storage.
as already found l1 (opcode) = 7, l2 (register) = 6.
There are 10 gigabytes of memory = 85899345920 bits.
l3 = log(85899345920) = 36.32 = 37 (rounding to upper bound).
thus, lb = l1+l2+l3 = 7+6+37 =50 bits

c)storage to storage
as already found, l1 (opcode) = 7 and l2,l3 (storage) = 37
thus, lc = l1+l2+l3 = 7+37+37 = 81 bits.

Given a 32 bit system, the no.of words required will be,
upper bound of length/32.
a) la/32 = 19/32 = 0.59 = 1 word.
b) lb/32 = 50/32 = 1.56 = 2 words.
c) lc/32 = 81/32 = 2.53 = 3 words.


-------------------------------------------------------------
B).
First lets calculate for the multiprocessing on eight parallel processors.
The eight processors can parallely sort the N names, with sorting N/8 names simultaneously. Then for merging, again parallel, 4 can be done, then two, then one.
Thus time taken for sorting N names is
t1 -> parallel sorting N/8 elements.
t1 = 10*(N/8)*log(N/8)

t2 -> merging 8 sorted list in parallel of each N/8 names
t2 = n1+n2 = N/8 + N/8 = N/4

t3 -> merging 4 sorted list in parallel of each N/4 names
t3 = n1+n2 = N/4 + N/4 = N/2

t4 -> finally merging 2 sorted list in parallel of each N/2 names
t4 = n1+n2 = N/2 + N/2 = N

Thus, total time T is sum of all the times
T1 = t1 + t2 + t3 + t4
T1 = 10*(N/8)*log(N/8) + N/4 +N/2 + N
T1 = 10*(N/8)*log(N/8) +(7N/8)

This is the time taken to do parallel sorting with 8 cores.

Now for a single processor, the whole sorting is done with the same processor and it takes time
T2 = 10*(N)*log(N)

These are the required algebraic equations.

Now, substituting the value N = 1,048,576 we get,
T1 = 10*(1048576/8)*log(1048576/8) + (7*1048576/8)
T1 = 10*(131072)*log(131072) + (7*131072)
T1 = 10*131072*17 + 7*131072
T1 = 23199744 = 2.3*10^7 units

T2 = 10*(1048576)*log(1048576)
T2 = 10*1048576*20
T2 = 209715200 = 2.09*10^8 units.

Thus as you can see, the time taken for parallel processing with 8 cores, gives us faster results since with 8 cores, the time is (T1) 2.3*10^7 and for single processor, the time is (T2) 2.0*10^8.

-------------------------------------------------------
C).
i)
Given 6 tracks and a time duration of TS for move across tracks
Time taken to read entire contents of disk = 6 TS

ii)
given speed of disk = TR
each track has 10 blocks.

Thus to read a randomly selected block, the time taken is (no.of blocks read/speed)
T = 10/TR

These are the required answers for all your questions. If you have any doubt, comment and I can help you further.
Cheers!

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.