program编程讲解、辅导C++语言、C++程序设计调试辅导Web开发|辅导Database

项目预算：开发周期：发布时间：要求地区：

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& 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 . 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

program编程讲解、辅导C++语言、C++程序设计调试 辅导Web开发|辅导Database

program编程讲解、辅导C++语言、C++程序设计调试辅导Web开发|辅导Database