On optimal parallelization of sorting networks

AbstractThis paper provides a unifying mathematical proof which replaces a mechanical certification of the optimal parallelization of sorting networks on a case basis. Parallelization of sequential program traces by means of semantic-preserving transformation is discussed in the literature in the context of a method for synthesis of systolic architecture. The issue of optimal parallelization is important in systolic design. The mathematical proof provides a better insight into the fundamental aspects of the transformation