| 二、 |
Two different search methods for a SORTED integer array are considered
on a computer with PAGED memory system: sequential search and binary search.
The following are some information you may need to answer the questions:
Integer size: 4 bytes
Array size: 16384 (1 -- 16384)
Page size: 4096 bytes
Time for searching and checking an item: 4 ms
Time for OS to handle page fault: 20 ms
Available pages for storing the array: 4 pages
Code is always resident in memory.
Initially, the array is residing on disk.
1 (5%) Estimate the time needed to search for 8194th item for both methods.
2 (5%) Estimate the time needed to search for 16300th item for both methods.
3 (5%) Estimate the time needed to search for 2045th item for both methods.
4 (10%) Suppose that the array is self-organized so that the items of
the top half (1 -- 8092) will be searched with probability 0.75 while
the bottom half with probability 0.25. In such case, which search method
will be better?
|
| 四、 |
Computer Organizations (50 ﹪)
| 1. |
(5﹪) What does RISC stand for? List 4 characteristics of the RISC
architecture. |
| 2. |
(5 ﹪) In describing the performance of a processor, what does MIPS
stand for? Explain why MIPS is not a good metric for performance comparison
in general? |
| 3. |
(5 ﹪) A floating point representation format is described as follows:
•The left most bit is the sign bit of the number with 0 indicating
a positive number.
•Following the sign bit is the 8-bit exponent using bias-127 representation.
•The rest is the 23-bit significand with the leading 1 hidden.
What is the decimal number represented by the following bit pattern?
1011 1111 0100 1000 0000 0000 0000 0000
|
| 4. |
(5﹪) Consider the function f(A,B,C,D) = Σ(0,2,4,5,10,11,13,15).
Find the standard SOP form and implement it using 2-input NAND gates
only. |
| 5. |
(15﹪) Consider a 6-stage pipeline for a load/store machine as follows:
| Stage |
Operation |
| IF |
Instruction Fetch |
| ID |
Instruction Decode |
| RF |
Register fetch |
| EX |
ALU operation and address calculation |
| MEM |
Memory access for load/store |
| WB |
Write result back into register file |
In order to accommodate multi-cycle operations, the EX unit is extended
to include 4 functional units. The number of cycles required by
each functional unit to complete an operation is as follows: the
integer unit, 1 cycle; the floating-point adder, 2 cycles; the multiplier,
3 cycles; and, the divider, 4 cycles. All, except the divider unit,
are fully pipelined. All data forwarding circuits are present. Given
the following code fragment, illustrate, using timing diagram, how
each instruction progresses through the pipeline. Identify all hazards
and indicate how they are resolved in your diagram. (Note: F n indicates
floating-point register n)
| DIV |
F0,F2,F4 |
// F0 ← F2 / F4 |
| MULT |
F6,F2,F4 |
// F6 ← F2*F4 |
| MULT |
F12,F8,F10 |
// F12 ← F8*F10 |
| ADD |
F4,F8,F10 |
// F4 ← F8+F10 |
| DIV |
F8,F4,F6 |
// F8 ← F4 / F6 |
| SUB |
F4,F4,F2 |
// F4 ← F4 - F2 |
|
| 6. |
(15﹪) A system supporting virtual memory uses 2 KB pages and 32
-bit address space. Its physical memory consists of a 256 MB main
memory and a 512 KB direct-mapped unified cache using 4-word blocks.
Design the organization of the TLB and the cache and illustrate
the process of going from a virtual address to a data item in cache
in your design. Your answer should have all the details, such as
the name and the width of every field, etc.
|
|