Project - Data Dependencies Distributed computing - Bernsteins conditions for Data Dependencies

In this project you will have to analyze the data dependencies between simple instructions. You will consider only simple arithmetic instructions that involve variables whose names are single letter of the English alphabet, the arithmetic operators (=, -, /, *), open and close parentheses, and the assignment operator. For example: a = b + ( c d / e). There will be a space between the variables, the operators and the open and close parentheses. Each simple instruction must have at least three distinct variables. You will design two separate algorithms, describe the algorithms using clear pseudocode and implement your algorithms in C/C++/Java, compile, test it, and submit BOTH the report (as a PDF file) and the programs. We do not care about the efficiency of the algorithms but each run of a program must terminate within 60 minutes if N=3 and M=4.

Algorithm Calculate

Problem: Given a simple instruction and a block of n instructions (n < 11), identify which instructions in the block can be executed in parallel to the simple instruction. Example 1 INPUT: Instruction: d = b + ( c d / e) Block: b = b * c c = c a a = a + b * c OUTPUT: Then the output should be: c = c a

a = a + b * c Algorithm Verify

Problem: You are given a number N < 11 instructions, identify all the pairs of instructions that can be executed in parallel.

Example 1 INPUT: Block: b = b * c d = c a a = a + b * c OUTPUT: The pairs of instructions that can be executed in parallel are: (b = b * c, d = c - a) Example 2 Block b = a * b * c c = c a a = a + b * c

OUTPUT The pairs of instructions that can be executed in parallel are: NONE