AN EQUIVALENT CLASS SOLUTION FOR A COMPLETE TEST OF A PARALLEL PROGRAM

With the advent of multi-core chips (multiple CPUs on a single chip) a fundamental shift in the design of programs is taking place. Previous use of parallel code in programs was limited to servers that contained multiple CPUs on separate chips. This idea is starting to change, with the majority of chips sold today containing multiple CPUs which require parallel code in software programs. The use of parallel code is not without problems. Non-parallel code executes programming statements in the same order, every time the same inputs are used. This result contrasts parallel code in the extreme. Identical inputs and conditions in no way to guarantee that parallel code will result in the same order of execution. For that reason testing parallel code is dramatically more difficult. It is because of this difficulty that I propose a solution that will allow a tester to guarantee a complete coverage of the shared memory parallel code through a series of non-exhaustive tests. This solution relies on the fact that the majority of the lines of code in the different threads don’t access the shared memory of program. This concept is what allows the creation of equivalent execution classes. Two execution schedules are equivalent if the critical sections that conflict with previously executed sections are in the same order in the schedule and the grouping of code between these sections are simply permutations of legal execution ordering