Case Study: Dependences and Instruction-Level Parallelism

Case study

The purpose of this case study is to demonstrate the interaction of hardware and software factors in producing instruction-level parallel execution. This case study presents a concise code example that concretely illustrates thevarious limits on instruction-level parallelism. By working with this case study, you will gain intu- ition about how hardware and software factors interact to determine the execution time of a particular type of code on a given system. A hash table is a popular data structure for organizing a large collection of data items so that one can quickly answer questions such as, “Does an element of value 100 exist in the collection?” This is done by assigning dataelements into one of a large number of buckets according to a hash function value generated from the data values. The data items in each bucket are typically organized as a linked list sorted according to a given order. Alookup of the hash table starts by determining the bucket that corresponds to the data value in question