Artificial deadlock detection in process networks for ECLIPSE

Kahn Process Network (KPN) is a popular model of computation for describing streaming applications. In a KPN model, processes communicate through unbounded unidirectional FIFOs. When theoretically unbounded FIFOs are implemented using finite memory, artificial deadlocks can occur due to one or more FIFOs having insufficient sizes. Generally a system designer must be able to make a design time trade-off between execution time and memory usage, preferably using no more memory than required for obtaining a certain execution time. But it is practically impossible to decide at design time, FIFO sizes that are sufficient to run the application without any artificial deadlocks. Hence there is a need for runtime mechanism for handling the artificial deadlock situations in process networks. Existing mechanisms detect artificial deadlocks only after all KPN processes block. This results in excessive blocking of processes and an application that appears to ’hang’. In this paper we present an improved mechanism for early detection of artificial deadlocks and its implementation on ECLIPSE (Extended CPU Local Irregular Processing ArchitecturE), an application domain specific architecture