write the Write a multi$-$threaded program using c code that will use the Sieve of Eratosthenes to find prime numbers. You must use a $$bit$-$array$$ to keep track of the values you eliminate$/$identify as non$-$prime numbers. Since you will be using PThreads, you will also have to use one or more mutexes to protect shared resources $($aka$,$ portions of the bit$-$array$).$ How and where you put your mutexes will affect the speedup you realize with your code. Do you want one mutex for the entire bit$-$array $($No$,$ you don$$t$),$ one for each bit $($No$,$ you most certainly do not!!!$),$ or something in between $(**$head nods vigorously$**)?$ I chose to use a structure that looks a lot like this:typedef struct BitBlock$\_$s $\{$ uint$32\_$t bits; pthread$\_$mutex$\_$t mutex;$\}$ BitBlock$\_$t;It allowed me to use fine level locks, but not so fine that all the time was spent in getting locks. The locks were not at such a coarse level that the threads became effectively serialized waiting on all the other threads to complete. It is interesting to see how the performance of the program is affected by changing from a uint$32\_$t to a uint$8\_$t$,$ uint$16\_$t$,$ or uint$64\_$t for the bits data member of the structure. If you are feeling really adventurous, gcc does have an unsigned $128$ bit integer type, $\_\_$uint$128\_$t $($yes$,$ the leading underscores are required$).$ A little Makefile magic makes it easy to switch between the various unsigned int types in the structure. As for using signed or unsigned, don$$t use signed. BTW, the uint$32\_$t $($and other sized types$)$ can be found in the stdint.h $($I recommend including it in your code$).$

When you are done writing your program, run it varying the number of threads to get an idea where the speedup starts to flatten out or even decline as the number of threads is

Macro

CS $532$ Lab$5$

Fall $2024$ Page $3$ of $5$ R$.$ Jesse Chaney

increased. If you don$$t see a speedup by changing the number of threads from $1-30,$ you are doing something wrong. You will also want to vary the upper bound on the prime numbers you generate to find out where creation of the threads startes to become helpful. If your code does not show any speed up when varied across multiple threads, spend the time getting your code to work better.

Your program must accept the following command line options. My code accepts more options than this, but these are the ones your code must accept and correctly handle.

Option Description$-$t # This is the number of threads that will be used to compute the number of prime numbers. If this value is not given on the command line, the default number of threads is $1.-$u # This is the upper bound on how large a prime number you will calculate. You should compute all the prime numbers between $2$ and the value given here. If this number is not given on the command line, compute the prime numbers up to $10,240.$ Note that is not the how many prime numbers to generate, but the largest value to test for primality. I strongly recommend you use an unsigned long for your upper bound.$-$h Show the help text and exit. Have something reasonable for this, like a listing of all the command line options. You can look at my program for an example.$-$v Verbose processing. This is really to help you follow what your code is doing. You need to accept this switch, have your code emit some diagnostics with this set. All the messages from the verbose output should be sent to stderr, NOT stdout.Allocate Memory: Use malloc$()$ for the bit vector and mutexes, then initialize them.

Process Primes: Use threads to calculate primes, output results, and clean up allocated memory.