program编程代做、代写C++语言、C++程序设计调试

日期：2020-11-18 11:36

Develop a C++ program that applies a parallel hash table

Design and implement a hash table with separate chaining and linear probing

Apply parallel programming concepts with the use of OpenMP

II. Prerequisites:

Before starting this programming assignment, participants should be able to:

Apply and implement class templates

Design, implement, and test medium programs in C++

Edit, build, debug, and run programs through a Linux environment

Describe the operations of a hash table

Describe the purpose of parallel programming

Identify parallel tasks

III. Overview & Requirements:

What is required?

For this project, you will implement functions for TWO hash table implementations.

Initially your implementations for both hash tables will be run in serial. A second version

of the “ProbingHash will be required, in which you add some parallel programming

constructs. You are being tasked with implementing both a separate chaining and a linear

probing hash table. The starting code base includes abstract class called “Hash”, which

the two concrete classes “ChainingHash” and “ProbingHash” are derived from. Please start

with the code. The file Hash.h includes a description of the interface and what you need to

implement with it.

The interface mostly follows the std::unordered_map interface, but it has been limited

a bit to avoid iterators and some of the more complex return type behaviors. The Hash.h

file has the actual interfaces, but here is the summary:

// Hash class interface notes

// ******************PUBLIC OPERATIONS*********************

// bool empty( ) --> Test for empty hash

// int size( ) --> Quantity of (non-deleted) elements in hash

// V& at( const K& k ) --> Returns the value with key k

// V& operator[]( const K& k ) --> Returns the value with key k

// int count( const K& key ) --> Returns the number of elements with key k

// bool emplace ( const K& key, V& value ) --> Adds element with key, true if successful

// bool insert( const pair<K, V>& pair ) --> Adds pair to hash, true if successful

// void erase( const K& k ) --> Removes all any (if any) entries with key k

// void clear( ) --> Empties the hash

// int bucket_count() --> Returns the number of buckets allocated (size

of the hash vector)

// int bucket_size( int n ) --> Returns the number of elements in bucket n (0,

1, or length of list if chaining)

// int bucket( const K& key ) --> Returns the bucket number of key (or throws

std::out_of_range if key not found)

// float load_factor( ) --> Returns the load factor of the hash

// void rehash( int n ) --> Resizes the hash to contain at least n buckets

// Resizes to next prime starting from n and

going up

Serial Implementation (50 pts – 25 pts/implementation)

In this part of the assignment, you will add features to the provided code for both types of

hash tables. Your initial solutions will be designed as usual, with a serial model. There are

notes in both .h files (“ChainingHash.h” and “ProbingHash.h”) about where you need to fill

in the stubbed functions or replace/update the ones that are there. Those public

interfaces cannot be changed, but you could add more public and private variables or

methods as you see fit.

Separate Chaining: This is a hash table where the data is stored in a vector of lists. Feel

free to use the C++ STL std::vector and std::list classes. You will also need to keep

track of the total number of elements stored in the hash for calculating “size.” Rehashing

is performed at a load factor of 0.75.

Linear Probing: This is a hash table with a single vector of elements, but it MUST do lazy

deletion. This means that every element in the table needs to be a std::pair (or some

other approach, I suppose). The pair needs to keep track if the bucket is empty, full, or

deleted and your code must use that information when probing and rehashing. You’ll need

to keep track of the total size of the hash table (total ‘full’, but not deleted buckets). This

is doing linear probing when probe(i’) = i. Rehashing is performed at a load factor of 0.75.

Both hash tables are only expected to work with integer keys, but it is templated all the

same. If you have got some time, please feel free to add some string key handling, but it

is not required.

Once you have finished your serial implementation, in main(), create an object of type

ChainingHash and one of type ProbingHash. Set the initial sizes of the tables to 101.

In order, insert values with keys 1 – 1,000,000. For simplicity, the key and value stored are

the same. For both tables, separately report the total amount of time, in seconds,

required to insert the values. Write the results to a file called “HashAnalysis.txt”. Search

for the value with key 177 in both tables. Report the time required to find the value in

each table by writing it to the file. Search for the value with key 2,000,000 in both tables.

Report the time required to find the value in each table by writing it to the file.  Remove

the value with key 177 from both tables. Report the time required to remove the value

with in each table by writing it to the file.  Also, write to the file the final size, bucket

count, and load factor of the hash for both implementations. Make sure that the results in

the file are clearly identifiable.

Parallel Implementation (20 pts)

Copy the contents of the “ProbingHash.h” file and place the copy in another file called

“ParallelProbingHash.h”. Rename the class in this file to ParallelProbingHash. Be sure

to include <omp.h>. Add OpenMP code to your implementation in the new file.

Specifically, add critical regions (#pragma omp critical) around the appropriate code

that performs insertions, deletions, and rehashing. Recall, within a critical region, only

one thread at a time can execute that code. This is one technique for mutual exclusion

that OpenMP supports.

In main(), create an object of type ParallelProbingHash. Set the initial size of the

table to 101.

Using one thread:

Set the number of threads (omp_set_num_threads()) to 1 initially. In an OpenMP

parallel region (#pragma omp parallel), in order, insert values with keys 1 –

1,000,000. Inside the parallel region make sure that the value for the iteration number of

the loop is shared among all threads. For simplicity, the key and value stored are the

same. Report the total amount of time, in seconds, required to insert the values to the

output file. Search for the value with key 177. Report the time required to find the value

by writing it to the file. Search for the value with key 2,000,000. Report the time required

to find the value by writing it to the file. Remove the value with key 177. Report the time

required to remove the value by writing it to the file. Make sure that the results in the file

are clearly identifiable.

Using the number of threads that matches number of cores on your system:

Change the number of threads to match the number of cores on your system. In an

OpenMP parallel region (#pragma omp parallel), in order, insert values with keys 1 –

1,000,000. Inside the parallel region make sure that the value for the iteration number of

the loop is shared among all threads. For simplicity, the key and value stored are the

same. Report the total amount of time, in seconds, required to insert the values to the

output file. Search for the value with key 177. Report the time required to find the value

by writing it to the file. Search for the value with key 2,000,000. Report the time required

to find the value by writing it to the file. Remove the value with key 177. Report the time

required to remove the value by writing it to the file. Make sure that the results in the file

are clearly identifiable.

Other Requirements (20 pts):

- In a comment block at the top of your main.cpp file, you must

address the following questions:

(6 pts) How did the serial implementations for the

ChainingHash and ProbingHash compare to each other? Did you

expect the time results obtained? Explain.

(8 pts) Compare the parallel and serial implementations for

the ProbingHash. Did the parallel implementations provide you

with the expected speedup? Explain.

(8 pts) What could you change in your parallel

implementations to improve performance and speedup? Explain.

Makefile Requirement (5 pts):

You are required to implement a Makefile for this assignment. Please make sure that you

add flags –g -Wall –std=c++11 -fopenmp when building. The -fopenmp is critical for the

OpenMP code!!!

IV. Submitting Assignments:

1. You must submit all required .h/.hpp, .cpp, .txt files and the Makefile.

2. Your project must build properly. The most points an assignment can receive if it

does not build properly is 65 out of 100.

V. Grading Guidelines:

This assignment is worth 100 points. Your assignment will be evaluated based on a

successful compilation and adherence to the program requirements. We will grade

according to the following criteria:

95 pts for adhering to requirements listed above – see each requirement for

point totals

5 pts for appropriate class and top-down design and adherence to proper

programming style established for the class and comments