We want to do multiple parallel implementations of the Quine-McCluskey boolean logic exact minimization algorithm. The goal of the project would be to examine tradeoffs for different parallel programming schemes. The QM algorithm takes as input a boolean function of n variables and returns a minimized list of implicants which will implement the function. For example, if we are given the following function: f = !a!b!c!d + !ab!c!d + !a!b!cd + !ab!cd + ab!cd + !abcd + abcd + a!bcd + abc!d + a!bc!d with the following Karnaugh map: 00 01 11 10 -- -- -- -- 00| 1 1 0 0 01| 1 1 1 0 11| 0 1 1 1 10| 0 0 1 1 Quine-McCluskey will tell us that the function can be implemented as: f = !a!c + bd + ac The algorithm is deceptively simple to run by hand, but to implement it efficiently is quite another matter, especially when considering the different ways of implementing it on a parallel processor. The basic operation of the algorithm is this: Construct a list of implicants. For n implicants, perform Theta(n^2) operations, producing a separate list of implicants, and then operate on that list of implicants. The number of lists is at most n. The major opportunity for parallelism that we have seen so far is that the lists can be generated dynamically: If we assign a process to each list, each process can take a stream of implicants from the previous list and generate a stream of implicants for successive lists. However, this is not sufficient to ensure good parallelism, for two main reasons: The number of implicants on the initial lists is (usually) much larger than the number of implicants on later lists, so if a process is assigned to each list, then the later ones will be starved for work; and, if there are more than n processors, they will not all be used if we simply assign a processor to each list, since there are at most n lists. The solution to these problems will be interesting to investigate. In more detail, the algorithm works as follows: First, generate a list of implicants. In our example from above, this is: 0000 0100 0001 0101 1101 0111 1111 1011 1110 1010 Next, find all the pairs of elements which differ in at most one element; compose a separate list of these elements, with one implicant for each element, with the term where they differ replaced by a -; keep track of the implicants used: 0000+ 0-00 0100+ 000- 0001+ 010- 0101+ 0-01 1101+ -101 0111+ 01-1 1111+ 11-1 1011+ -111 1110+ 1-11 1010+ 111- 101- 1-10 Note that implicants which have already been used can still be used in other pairs; this is essential to the correctness of the algorithm, corresponding to overlapping implicants in a Karnaugh map. The next step is to generate another implicant list. 0000+ 0-00+ 0-0- 0100+ 000-+ 0-0- 0001+ 010-+ -1-1 0101+ 0-01+ -1-1 1101+ -101+ 1-1- 0111+ 01-1+ 1-1- 1111+ 11-1+ 1011+ -111+ 1110+ 1-11+ 1010+ 111-+ 101-+ 1-10+ Note that (0-00,0-01) and (000-,010-) both reduce to (0-0-); this is also the case for some other pairs of implicants. Two choices for the implementation of collisions such as these are: Only add to a list if the specified implicant is not already present in the list; or, discard any duplicate implicants in the final output. The next step in the algorithm is to look once more for implicants which differ in only one term. However, there are no such implicants, so it is time to move on to the next phase of the algorithm, which is finding all the prime implicants -- that is, the implicants which were not collected into a pair. These are all the implicants which do not have a + beside them. In this example, the set of prime implicants is exactly the same as the set of elements in the right list, but in general, there may be prime implicants in any of the lists, and all of these are used for output. The list of prime implicants in this example is: (0-0-,-1-1,1-1-), meaning that the function can be expressed as !a!c + bd + ac, as can easily be verified by looking at the Karnaugh map above. We feel that this algorithm is appropriate to the project because: - It is significantly hard, and it proposes some significant design challenges, especially relating to load balancing. The difficulty, however, is not concentrated in the algorithm itself but in the parallelization of it, so that it affords a real opportunity to focus on parallelization. - It is fundamentally different from the Traveling Salesman problem, in that there is no obvious way to express it as a tree, and it involves significant communication. - The implementation involves a mix of communication and storage which lends itself well to shared address space and message passing models of computation (perhaps even more well than TSP). We also considered the following projects: - neural nets: Rejected because they're dominated by communication, not computation, and there's really not a whole lot to be done. (This would be a straightforward, uninteresting application of message passing.) - imagine processing: probably embarassingly parallel, not a lot of room for improvement - a novel compression algorithm (too detailed to describe here): the difficulty is focused in the initial implementation, not in the parallelism - A* search: too similar to TSP