C Programming - Multithreading Conversion

[ronnn]

Hello and Happy Thanksgiving! (if you celebrate)
I am in need of some guidance in regards to a program that I need to edit in order for it to have multithreading support. The problem is as follows:

I was given a circuit-satisfactory program that would compute whether a circuit was satisfiable or not.
. The circuit contains AND, OR, and NOT gates. It has 16 inputs from left side, each of which can take either 0 or 1. So there are 2^16=65,536 different combinations of inputs. The output on the right side indicate whether a given combination satisfies the circuit.

Your task is to convert this program to a multithreaded version. An additional requirement of this program is that you only count and print out the combinations where the second least significant bit is a 1.

Your program should take an integer between 1 and 128 as the command-line argument. You are going to create p threads (in additional to the main thread) that divide the 65,536 number of combinations among them. For example, if p=3, each thread would be responsible for roughly 65,536/3 number of iterations (if it's not divisible, some threads can end up with one more iteration than the others).

If a thread finds a combination that satisfies the circuit, it should print out the combination (like in the given sequential version, but remember to do so only when its second least significant bit is a 1), along with the thread id (a number between 0 and p-1). In the end, the main thread should print out the run time and the total number of combinations that satisfy this circuit.

As I began working on the assignment I hit a road block trying to figure out how to divide the different iterations among the p-number of threads. I'm also unsure if the threads should be created in a separate loop THEN run a loop with 65,636/p-threads. Any sort of help is greatly appreciated!

Here's what I have so far:

 #include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <pthread.h>
/* Return 1 if 'i'th bit of 'n' is 1; 0 otherwise */
#define EXTRACT_BIT(n,i) ((n&(1<<i))?1:0)
 
int count = 0;
 
int check_circuit (int z) {
  int v[16];        /* Each element is a bit of z */
  int i;
 
  for (i = 0; i < 16; i++) v[i] = EXTRACT_BIT(z,i);
  if ((v[0] || v[1]) && (!v[1] || !v[3]) && (v[2] || v[3])
      && (!v[3] || !v[4]) && (v[4] || !v[5])
      && (v[5] || !v[6]) && (v[5] || v[6])
      && (v[6] || !v[15]) && (v[7] || !v[8])
      && (!v[7] || !v[13]) && (v[8] || v[9])
      && (v[8] || !v[9]) && (!v[9] || !v[10])
      && (v[9] || v[11]) && (v[10] || v[11])
      && (v[12] || v[13]) && (v[13] || !v[14])
      && (v[14] || v[15]) ) {
    printf ("%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d\n",
	    v[0],v[1],v[2],v[3],v[4],v[5],v[6],v[7],v[8],v[9],
	    v[10],v[11],v[12],v[13],v[14],v[15]);
    return 1;
  } else return 0;
}
 
 
void * multiCircuit ( void * tid)
{
    long * myID = (long *) tid;
    int z;
    z = check_circuit(count);
 
    printf("%d was found by %ld\n", z, *myID);
    return 0;
}
 
 
 
 
 
 
int main (int argc, char *argv[]) 
{
    int arg;
    arg = atoi(argv[1]);
    if(argc != 2)
    {
        printf("Please enter the number of threads you wish to initialize\n");
        return 1;
    }
    if(arg < 1 || arg > 128)
    {
        printf("Please enter a number of threads between 1-128\n");
        return 11;
    }
 
   if (argc == 2 && (arg > 1 && arg < 128)){
    pthread_t threads[arg];
    pthread_mutex_t lock;
    int  i, thread_NUM;
    thread_NUM = arg;
    struct timeval t1, t2;
 
  gettimeofday(&t1, 0);
 
    for (i = 0; i < 65536/thread_NUM; i++){
        pthread_create(&threads[i], NULL, multiCircuit, (void *) &threads[i]);
        pthread_mutex_lock(&lock);
    //count += check_circuit (i);
        count++;
    gettimeofday(&t2, 0);
        pthread_mutex_unlock(&lock);
    }
 
  printf ("Execution time %fs\n", (t2.tv_sec-t1.tv_sec)+(t2.tv_usec-t1.tv_usec)*1e-6);
  printf ("There are %d solutions\n", count);
 
       pthread_exit(NULL);
    }
 
    return 0;
}

[George P]

C11 added a thread library, <threads.h>. <pthreads.h> is a POSIX (Linux only) library.

[ronnn]

oh, cool! I am doing the development on a Mac though so I do not think it matters too much, I could be wrong though haha.

[George P]

Mac or not, you'll probably still be better off using the C11 thread support library.
https://en.cppreference.com/w/c/thread

Good luck.

[jonnin]

pthreads is (or was?) portable and could work on any platform, from what I recall. I know I used it on windows in the xp era a fair bit, for some code that needed to run on unix and windows both. But it isn't the best choice now, as noted. I don't recall if we had to do something to make it work or not -- it was long ago, I just know we had it working.