[This is my write-up for Intel Threading Challenge 2010. You may download the code for Microsoft Visual C++ at the bottom of the page]

Problem Statement

Data Structure Description: To support the computation of the problem described below, implement a thread-safe data structure that implements multiple ordered lists. Lists within the structure are indexed starting at 0 and proceeding up to one less than the number of lists created for the structure. The following base thread-safe functions/methods are to be implemented for the problem described below:

BOOL initialize (int num_lists)

-- Create multi-list structure with num_lists empty lists.

void insert( unsigned int list_num, <T> item)

-- Add item to the end of the list_num list.

BOOL delete (<T> item, unsigned int list_num)

-- Remove the first instance of item on the list_num list. Return TRUE if the item was found and removed, FALSE to indicate the item is not on the list.

BOOL find (<T> item, unsigned int list_num)

-- Determine if there is at least one instance of item on the list_num list. Return TRUE if the item was found, FALSE to indicate the item is not on the list.

BOOL peek (unsigned int list_num, unsigned int position, <T*> item)

-- Return the value of the item in the current position, using ‘1’ as the position of the first item on a non-empty list, from the list_num list. Return TRUE if the list contains at least position elements and the item was returned; FALSE to indicate the list did not contain enough elements.

Problem Description: Write a threaded program to generate and populate a collection of ordered lists using the multi-list structure described above. From the data stored in the lists, compute the rank of each of the integers found in the multi-list structure. The rank of a list item is based on its position within the lists using the following algorithm:

R = 1

do {

All elements at the front of each list are assigned rank R

Remove each instance of rank R items from every list

R++

} until all lists are empty

Input to the program will come from the command line and contain two file names. The first file will hold data to be used to generate the initial data within the multi-list structure and the second will be the file to write out the ranks of all items generated.

List Generation: Use a linear congruential pseudo-random number generator (PRNG) to initially populate the lists. Use the following relation for the PRNG:

X[i+1] = (a*X[i] + b) mod m

…where the initial seed value is X[0] and the results of the relation are fed back as the seed for the next number calculation.

Part of the input to the application will be the 4-tuple (seed, a, b, m). Using the input values, generate multiple 4-tuples that will in turn be used to generate values to be stored on the list within the multi-list structure. The following serial algorithm describes how to use the PRNG function for this purpose.

for (i = 0..NUM_LISTS-1) {

X0[i] = PRNG(&seed, a, b, m);

A[i] = PRNG(&seed, a, b, m);

B[i] = PRNG(&seed, a, b, m);

M[i] = PRNG(&seed, a, b, m);

}

for (i = 0..NUM_LISTS-1) {

if (M[i] != 0) {

for (j = 1..NUM_ITEMS) {

int item = PRNG(&X0[i], A[i], B[i], M[i]);

insert(i, item);

}

}

}

Next page: Multi-list Interface and Implementation