Reference no: EM132251790

Question: 1) You have been assigned the task of computing the sum of 1,000 four-digit numbers as rapidly as possible. You hold in your hands a stack of 1,000 index cards, each containing a single number, and you are in charge of 1,000 expert accountants, each with a calculator. You may choose to use the services of any number of accountants. The accountants are sitting at desks in a cavernous room. The desks are organized in to 25 rows and 40 columns. Each accountant is able to pass cards to the four accountants nearest him - in front, in back, to his left, and to his right.

a. Describe a fast method of distributing cards to accounts.

b. Describe a fast method of accumulating subtotals generated by active accountants into a grand total.

c. Explain why 1,000 accountants cannot perform the task 1,000 times faster than on accountant.

d. Find another way to arrange the desks of the accountants to reduce the time needed to distribute cards and collect subtotals. Describe the new desk arrangement, the new communication pattern, and the new estimate for time spent distributing cards and accumulating subtotals.

2) A copy machine's feeder tray holds pages to be copied. Assume that it takes 5 second to load a new group of pages in the feeder before copying and 10 seconds to unload the original and the copies after copying. If the copier takes 4 seconds to print the first page of a group and 1 second to print every subsequent page, what is the minimum capacity of the feeder tray necessary to ensure that the effective throughput of the copier asymptotically approaches 40 pages per minute as the length of the original document increases?

3) Explain how a queue, implemented in hardware in the CPU, could be used to improve the performance of a write-through cache.

4) Assume that the main memory of a small computer is composed of 1 Megabytes, which are mapped into a 4-kilobyte cache. The cache is 4 way set associative. Blocks in main memory and block frames in the cache contain 32 bytes each.

a) Draw a diagram showing the organization of the cache indicating how physical addresses are related to the cache addresses.

b) To what block in main memory does the address 25320 belong to?

c) What memory addresses does the block 6234 contain in main memory?

d) To which set in the cache memory does the block 6234 map to?

5) Assume a hypercube of 256 nodes in the following questions:

a) What is he maximum number of hops required to reach the farthest node in the system?

b) How many neighbors does each node have?

c) Identify all the neighbors of the node 100.

d) What is the length of the shortest path between node 70 and node 12?