The ACM/IEEE conference has initiated a new award, the Test of Time award, which recognizes a paper from a past conference that has deeply influenced the HPC discipline. It is a mark of historical impact, and requires clear evidence that the paper has changed HPC trends. The inaugural Test of Time Award, selected from papers published at Supercomputing between 1988 and 2003, will be to William Pugh, for the 1991 paper "The Omega Test: a fast and practical integer programming algorithm for dependence analysis."

The Omega test was one of the first papers to suggest general use of an exact algorithm for array data dependence analysis, a problem which is NP-complete, and to show that is was very fast in practical use. More importantly, it also could use general affine constraints (as opposed to many existing algorithms which could only use constraints in certain pre-defined patterns), and could produce symbolic answers, rather than just yes/no answers. This work was the foundation of the Omega project and library, which significantly expanded the capabilities of the Omega test and added to the range of problems and domains that it could be applied to. 

This talk will be a preview of the award talk to be giving at Supercomputing 2013, and will review the Omega test's history, the research difficulties that had to be overcome to provide the result and the impact that the paper has had, both in HPC and beyond.