Hardware Reference
In-Depth Information
9.
Can you envision circumstances in which an assembly language permits a label to be
the same as an opcode (e.g.,
MOV
as a label)? Discuss.
10.
Show the steps needed to look up Ann Arbor using binary search on the following list:
Ann Arbor, Berkeley, Cambridge, Eugene, Madison, New Haven, Palo Alto, Pasadena,
Santa Cruz, Stony Brook, Westwood, and Yellow Springs. When computing the mid-
dle element of a list with an even number of elements, use the element just after the
middle index.
11.
Is it possible to use binary search on a table whose size is prime?
12.
Compute the hash code for each of the following symbols by adding up the letters (A =
1,B=2,etc.) and taking the result modulo the hash table size. The hash table has 19
slots, numbered 0 to 18.
els, jan, jelle, maaike
Does each symbol generate a unique hash value? If not, how can the collision problem
be dealt with?
13.
The hash coding method described in the text links all the entries having the same hash
code together on a linked list. An alternative method is to have only a single
n
-slot ta-
ble, with each table slot having room for one key and its value (or pointers to them). If
the hashing algorithm generates a slot that is already full, a second hashing algorithm
is used to try again. If that one is also full, another is used, and so on, until an empty is
found. If the fraction of the slots that are full is
R
, how many probes will be needed,
on the average, to enter a new symbol?
14.
As technology progresses, it may one day be possible to put thousands of identical
CPUs on a chip, each CPU having a few words of local memory. If all CPUs can read
and write three shared registers, how can an associative memory be implemented?
15.
The x86 has a segmented architecture, with multiple independent segments. An
assembler for this machine might well have a pseudoinstruction
SEG N
that would
direct the assembler to place subsequent code and data in segment
N
. Does this
scheme have any influence on the ILC?
16.
Programs often link to multiple DLLs. Would it not be more efficient just to put all the
procedures in one big DLL and then link to it?
17.
Can a DLL be mapped into two process' virtual address spaces at different virtual ad-
dresses? If so, what problems arise? Can they be solved? If not, what can be done to
eliminate them?
18.
One way to do (static) linking is as follows. Before scanning the library, the linker
builds a list of procedures needed, that is, names defined as
EXTERN
in the modules
being linked. Then the linker goes through the library linearly, extracting every proce-
dure that is in the list of names needed. Does this scheme work? If not, why not and
how can it be remedied?
19.
Can a register be used as the actual parameter in a macro call? How about a constant?
Why or why not?
