Deadlock-freeness of hexagonal systolic arrays

Abstract

With the re-emergence of parallel computation for technical applications in these days also the classical concept of systolic arrays is becoming important again. However, for the sake of their operational safety, the question of deadlock must be addressed. For this contribution we used the well-known Roscoe-Dathi method to demonstrate the deadlock-freeness of a systolic array with hexagonal connectivity. Our result implies that it is theoretically safe to deploy such arrays on various platforms. Our proof is valid for all cases in which the computational pattern (input-output-behaviour) of the array does not depend on the particular values (contents) of the communicated data.