![Multi-threaded hash tree Assignment](https://universalassignment.com/wp-content/uploads/2022/11/Our-School-Has-The-Green-Playground-3-1024x577.png)
In this project, you will write a multi-threaded program to compute a hash value of a given file. The size of the file can be very large. So, there is a need for the program to be multi-threaded to achieve speedup. While one thread reads a part (block) of the file, other threads can compute hash values of already read blocks.
Binary tree threads
Create a binary tree of threads where each thread will compute the hash value
Hash value
The hash value of a string (very long) is a fixed length numeric value. Hash values are typically expressed in hex digits and can be long. In this project we will restrict the hash value type to a 32-bit unsigned integer. A hashing algorithm will read the input string (file) and produce a hash value. There are many hashing algorithms in the literature. For this project we will use Jenkins one_at_a_time hash described in
One of the uses of hash value is to check the integrity of the data (file, database, etc.). One can think of a hash value of a file as a fingerprint of the file. If the file is modified, then the hash value also changes. By comparing the new and old hash values one can easily detect that the file was modified.
Computation of a hash value of a large file (several giga bytes in size) may take a while. Hence a need for a multi-threaded program.
Part 1: Multi-threaded hashing
A file can be divided into multiple blocks. The basic unit of accessing a file on a i/o device is a block. Assume there are n blocks, m threads, and n is divisible by m. Each thread can compute the hash value of n/m consecutive blocks. Several of these hash values are then combined to form a string whose hash value can be computed as before. These steps can be repeated till one final hash value remain.
A complete binary tree of threads should be created. Each leaf thread will compute the hash value of n/m consecutive blocks assigned to it and return the hash value to its parent thread (through pthread_exit() call). An interior thread will compute the hash value of the blocks assigned to it, and then wait for its children to return hash values. These hash values should be combined to form a string: <computed hash value + hash value from left child + hash value from right child>. (Note that the + sign here means concatenation and not addition. Also, if the interior thread has no right child, only the hash value of the interior thread and the hash value from the left child are combined.) The interior thread then computes hash value of the concatenated string as before and returns the value to its parent, The value returned by the root thread is the hash value of the file.
How to assign blocks to threads?
Each thread is assigned a number when it is created. The number of root thread is 0. For a thread with number i, the number of its left child is 2 * i + 1, and the number of its right child is 2 * i +
2. For a thread with number i, n/m consecutive blocks starting from block number i * n/m are assigned. For example, let n = 100 and m = 4. Then thread 0 will be assigned blocks 0 through 24, thread 1 will be assigned blocks 25 through 49, thread 2 will be assigned blocks 50 through 74, and thread 3 will be assigned blocks 75 through 99.
Usage and hints
Name your program htree.c. The usage is:
htree filename num_threads
‘filename’ is the name of the input file whose hash value needs to be computed. ‘num_threads’ is
the number of threads to be created.
Assume the block size to be 4096 bytes. Number of blocks can be found from the file size in bytes. Check fstat() to find the file size.
You can read any block from the input file using lseek(0 and read(). But there is an easier way to read blocks from a file using mmap(). Check the man page for mmap().
You can use sprintf() to convert an uint to string.
Part 2: Experimental study
The main goal of this study is to find speedup achieved when the number of threads is increased for various input files. For each input file, find the time taken to compute the hash value for 1, 4, 16, 32, 64, 128, and 256 threads. To run 256 threads, increase ulimit -u to 256.
Plot a graph with time on y-axis, and #threads on x-axis for each input file. Plot another graph with speedup on y-axis and #threads on x-axis for each input file.
speedup = (time taken for single thread)/(time taken for n threads)
Write a short report on what you observe. It is expected that the time taken to compute hash value decrease when the number of threads increase. Does it always happen? What is the speed-up achieved when the number of threads increased? Is the speedup proportional to the number of threads increased? Also, briefly describe the experimental set-up at the beginning of your report. (Command ‘lscpu’ provides relevant information for this)
Write a high-quality report. You should showcase the report in your job interview.
Other Requirements
Error handling is an important concept in system programming. In general, there should be no circumstances in which your C program will core dump, hang indefinitely, or prematurely terminate. Therefore, your program must respond to all input in a reasonable manner; by “reasonable”, we mean print an understandable error message and either continue processing or exit, depending upon the situation.
So, check the input for errors. Check the return values of function calls. Display appropriate error messages.
CODE THAT I HAVE SO FAR
Issues: Does not run for files over 2GB runs into segmenation fault
The multi-threading is not working as expected – each thread should calculate the hash and return the hash value to the parent to further combine the hash
As the threads are increased the time elapsed is increasing or the same as 1 thread regardless of the file size (1MG, 1GB, 2GB)
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>
#include <errno.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <pthread.h>
#include <string.h>
#include <sys/mman.h>
#define BSIZE 4096
struct node
{
uint32_t hash;
int32_t num_blocks;
int32_t start_block;
int32_t end_block;
pthread_t thread_id;
struct node *left_child;
struct node *right_child;
};
struct thread_args
{
struct node *node_ptr;
int32_t thread_num;
int32_t num_threads;
uint8_t *file_ptr;
};
struct stat file_info;
void usage(char *);
uint32_t jenkins_one_at_a_time_hash(const uint8_t *, uint64_t);
void compute_hash(struct node *, uint8_t *);
void *compute_node_hash(void *);
void process_inputs(char *file_name, uint8_t **file_ptr, uint32_t *num_blocks, uint32_t *num_threads, struct stat *file_info);
int main(int argc, char **argv)
{
// int32_t fd;
uint32_t num_threads, num_blocks;
uint8_t *file_ptr;
// struct stat file_info;
struct node *root;
struct timespec start, end;
double elapsed;
// input checking
if (argc != 3)
usage(argv[0]);
num_threads = atoi(argv[2]);
// input checking and file processing
process_inputs(argv[1], &file_ptr, &num_blocks, &num_threads, &file_info);
clock_gettime(CLOCK_MONOTONIC, &start);
// construct hash tree
root = (struct node *)malloc(sizeof(struct node));
root->num_blocks = num_blocks;
root->start_block = 0;
root->end_block = num_blocks – 1;
root->left_child = NULL;
root->right_child = NULL;
compute_hash(root, file_ptr);
// create threads and compute hash values
struct thread_args *args = (struct thread_args *)malloc(num_threads * sizeof(struct thread_args));
for (uint32_t i = 0; i < num_threads; i++)
{
args[i].node_ptr = root;
args[i].thread_num = i;
args[i].num_threads = num_threads;
args[i].file_ptr = file_ptr;
pthread_create(&args[i].node_ptr->thread_id, NULL, compute_node_hash, (void *)&args[i]);
}
// wait for threads to complete
for (uint32_t i = 0; i < num_threads; i++)
{
pthread_join(args[i].node_ptr->thread_id, NULL);
printf(“tnum %d hash computed %” PRIu32 “\n”, i, args[i].node_ptr->hash);
printf(“tnum %d hash from left child %” PRIu32 “\n”, i, args[i].node_ptr->left_child->hash);
printf(“tnum %d hash from right child %” PRIu32 “\n”, i, args[i].node_ptr->right_child->hash);
printf(“tnum %d hash sent to parent %” PRIu32 “\n”, i, args[i].node_ptr->hash);
}
// end_time = clock();
clock_gettime(CLOCK_MONOTONIC, &end);
printf(“num_threads = %u\n”, num_threads);
printf(“Blocks per Thread = %u\n”, num_blocks / num_threads);
printf(“hash value = %” PRIu32 “\n”, root->hash);
elapsed = (end.tv_sec – start.tv_sec) + (end.tv_nsec – start.tv_nsec) / 1000000000.0;
printf(“Time taken: %f seconds\n”, elapsed);
// clean up
munmap(file_ptr, file_info.st_size);
free(root);
free(args);
return 0;
}
void compute_hash(struct node *node_ptr, uint8_t *file_ptr)
{
if (node_ptr->num_blocks == 1)
{
node_ptr->hash = jenkins_one_at_a_time_hash(file_ptr + node_ptr->start_block * BSIZE, BSIZE);
return;
}
// divide the node into two halves
node_ptr->left_child = (struct node *)malloc(sizeof(struct node));
node_ptr->right_child = (struct node *)malloc(sizeof(struct node));
node_ptr->left_child->num_blocks = node_ptr->num_blocks / 2;
node_ptr->left_child->start_block = node_ptr->start_block;
node_ptr->left_child->end_block = node_ptr->start_block + node_ptr->left_child->num_blocks – 1;
node_ptr->left_child->left_child = NULL;
node_ptr->left_child->right_child = NULL;
node_ptr->right_child->num_blocks = node_ptr->num_blocks – node_ptr->left_child->num_blocks;
node_ptr->right_child->start_block = node_ptr->left_child->end_block + 1;
node_ptr->right_child->end_block = node_ptr->end_block;
node_ptr->right_child->left_child = NULL;
node_ptr->right_child->right_child = NULL;
// compute hash values of child nodes
compute_hash(node_ptr->left_child, file_ptr);
compute_hash(node_ptr->right_child, file_ptr);
// combine hash values of child nodes
node_ptr->hash = node_ptr->left_child->hash + node_ptr->right_child->hash;
}
void *compute_node_hash(void *arg)
{
struct thread_args *args = (struct thread_args *)arg;
struct node *node_ptr = args->node_ptr;
uint8_t *file_ptr = args->file_ptr;
int32_t thread_num = args->thread_num;
int32_t num_threads = args->num_threads;
if (node_ptr->left_child == NULL && node_ptr->right_child == NULL)
{
uint32_t block_start = node_ptr->start_block;
uint32_t block_end = node_ptr->end_block;
uint32_t block_size = block_end – block_start + 1;
uint32_t num_blocks_per_thread = node_ptr->num_blocks / num_threads;
uint32_t thread_block_start = block_start + thread_num * num_blocks_per_thread;
uint32_t thread_block_end;
if (thread_num == num_threads – 1)
thread_block_end = block_end;
else
thread_block_end = thread_block_start + num_blocks_per_thread – 1;
uint32_t thread_block_size = thread_block_end – thread_block_start + 1;
uint8_t *thread_block_ptr = &file_ptr[thread_block_start * BSIZE];
node_ptr->hash = jenkins_one_at_a_time_hash(thread_block_ptr, thread_block_size * BSIZE);
}
else
{
pthread_t left_thread_id, right_thread_id;
struct thread_args left_args, right_args;
left_args.node_ptr = node_ptr->left_child;
right_args.node_ptr = node_ptr->right_child;
left_args.thread_num = thread_num;
right_args.thread_num = thread_num;
left_args.num_threads = num_threads;
right_args.num_threads = num_threads;
left_args.file_ptr = file_ptr;
right_args.file_ptr = file_ptr;
pthread_create(&left_thread_id, NULL, compute_node_hash, (void *)&left_args);
pthread_create(&right_thread_id, NULL, compute_node_hash, (void *)&right_args);
pthread_join(left_thread_id, NULL);
pthread_join(right_thread_id, NULL);
node_ptr->hash = node_ptr->left_child->hash + node_ptr->right_child->hash;
}
return NULL;
}
uint32_t jenkins_one_at_a_time_hash(const uint8_t *key, uint64_t length)
{
uint32_t hash, i;
for (hash = i = 0; i < length; ++i)
{
hash += key[i];
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return hash;
}
void usage(char *program_name)
{
fprintf(stderr, “Usage: %s <input_file> <num_threads>\n”, program_name);
exit(EXIT_FAILURE);
}
void process_inputs(char *file_name, uint8_t **file_ptr, uint32_t *num_blocks, uint32_t *num_threads, struct stat *file_info_ptr)
{
int32_t fd;
struct stat file_info;
// input checking
if (*num_threads <= 0)
{
fprintf(stderr, “Invalid number of threads.\n”);
exit(EXIT_FAILURE);
}
// open input file
fd = open(file_name, O_RDWR);
if (fd == -1)
{
perror(“open failed”);
exit(EXIT_FAILURE);
}
// use fstat to get file size and calculate number of blocks
if (fstat(fd, &file_info) == -1)
{
perror(“fstat failed”);
exit(EXIT_FAILURE);
}
*num_blocks = (uint32_t)(file_info.st_size / BSIZE);
if (file_info.st_size % BSIZE != 0)
(*num_blocks)++;
// mmap file into memory
*file_ptr = (uint8_t *)mmap(NULL, file_info.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
if (*file_ptr == MAP_FAILED)
{
perror(“mmap failed”);
exit(EXIT_FAILURE);
}
close(fd);
*file_info_ptr = file_info;
}
![Order Now](https://universalassignment.com/wp-content/uploads/2022/04/Order-Now-Assignment.png)
Get expert help for Multi-threaded hash tree Assignment and many more. 24X7 help, plag free solution. Order online now!