Search

In the late 1980's, I was recovering from a long stint as the manager of Paris University computing facility (yes, there were still computing facilities, and PCs were just coming of age) and I was teaching old fashioned automatic parallelization to postgraduate students. I had heard of scalar expansion and privatization, and it was a natural question whether it could be extended to arrays. I first concocted partial solutions - for instance, valid only for the innermost loop - and then decided to try for the general case: converting array accesses to single assignment form. I soon realized that this implied finding the source, or last write before a given read, and that the solution must be a function of the position of the read in the temporal execution of the program. It was obvious that this could not be done for arbitrary complex programs, hence I specified a set of restriction: the polyhedral model. I also introduced the execution order, now known as the 'happens-before' relation. Finding the last write then became an integer programming problem with some unfamiliar features: lexicographic order took the place of the economic function, the problem had to be solved exactly, and the coordinates of the read operation were acting as parameters. Hence, I had first to build PIP (a parametric integer programming tool [2]) before solving my problem. PIP was developed on a 80286 PC, using Borland TurboC and LeLisp.It then took me about two years to have an improved form of the ICS paper published by a journal [3]. Here, the emphasis was more on single assignment conversion and its use for program comprehension. I also formalized a comparison algorithm, which is needed when there are several potential sources. But it was not until [4] that I managed to prove its termination.Meanwhile, the ICS paper had attracted attention from the other side of the Atlantic. Most important was Bill Pugh's work [6], in which the problem was reformulated in term of affine relations, and solved by Bill's own linear programming tool, Omega. I remember that we exchanged our benchmarks, and found that our results were equivalent. An early example of reproducible research!!