An Implementation of Process Networks in JavabyArnab BasuandH.P. Vijay KishenLiterature SurveyEmbedded Software Systems (EE382C)AbstractProcess networks are networks of sequential processes connected by channels behavinglike FIFO queues. These are used in signal and image processing applications that need torun in bounded memory for infinitely long periods of time dealing with possibly infinitestreams of data. In general, the termination and boundedness of process networks are notdecidable in finite time. Parks suggests an algorithm that provides a way of executingthese models in bounded memory, if a bounded memory schedule exists. The objectivesof this literature survey are to study the various Process Network models in existence andto implement a Process Network model in Java, including Parks’ bounded memoryscheduler.IntroductionProcess Networks is a determinate, concurrent computational model. The PNmodel, a network of nodes interconnected via arcs, is well suited for implementingcomputation intensive, real time applications typically present in signal and imageprocessing systems. This class of applications involves computing number of partialresults on infinite streams of data in near real time. Managing concurrency in theseapplications becomes a significant part of these applications.The Java language provides threads, which are concurrent sequential programsthat can share data, precisely to deal with such applications. However, programming withthreads in their raw form can easily lead to errors that are difficult to diagnose. Inparticular, the Java language does not define precisely how threads are scheduled. This isdependent on the implementation. Consequently, writing multithreaded applications thatbehave identically across multiple implementations requires painstaking care andattention to detail.In the first section a brief introduction to the different Process Network (PN)models is given, in the second section reasons for choosing Java as the implementationlanguage are discussed and in the last section a brief discussion of the problems that thisimplementation will face are presented.Process NetworksThe concurrent processes in a PN communicate using unidirectional FIFO queues.Each FIFO queue provides storage for a node’s output and input for the downstreamnode. Using the syntax of directed multigraphs, each node represents a process and eachedge represents a FIFO queue. When a process attempts to read an empty queue, theprocess blocks. This guarantees determinacy [1], provided that the processes areinherently determinate and do not have any shared or global variables that are beingaccessed by other processes that might introduce indeterminacy into the model.Schedulability and boundedness of Process Networks are undecidable. The first PN model by Kahn [1] has a possibility of infinite FIFO queue sizesbetween arcs. In this model, the functions are treated as functions that map every inputsequence onto an output sequence. The processes in this model are Monotonic, functionswhich move in only one direction as the input increases. As a consequence, the nodes donot need to have all of the input ready before they start computing the output. The‘History’ of a channel is defined as the sequence of tokens that have been written to andread from the channel. This model can be proven to be determinate, if the histories of theinternal and output channels in the system solely depend on the history of the inputchannel. In a Kahn PN, it is not possible to predict whether the model will terminate infinite time and will be able to execute in finite memory. When deadlock occurs i.e. whenall nodes are blocked while trying to read from their respective channels, it happensbecause of the PN program and is not related to any schedule chosen to execute theprogram.Another variation of process networks called Dataflow process networks [2],circumvents the problem of infinite queue sizes between nodes by adding certain rules toKahn’s model. The following rules when added will yield a bounded schedule if oneexists:• Block when attempting to write to a full queue.• Block when attempting to read from an empty queue.• When deadlock (due to blocking writes) occurs increase the size of the smallestsize queue so that the deadlock is removed, i.e. the producer associated with thisarc can fire.The first constraint translates into an initial capacity being assigned to every FIFOqueue in the graph. This has the possibility of introducing Artificial Deadlock into themodel. This occurs when the nodes in the graph are blocked due to writes to the fullqueues. The third rule is to take care of such scenarios whereby the size of the smallestqueue is increased so that deadlock is removed. The two requirements added by Parks forthe dynamic scheduler associated with this kind of dataflow model follow:a) Complete Execution – the scheduler should implement a complete execution ofthe process network program. If the program is non-terminating, then it should beexecuted forever without terminating. andb) Bounded Execution – the scheduler should if possible execute the process networkprogram so that only a bounded number of tokens ever accumulate on any of thecommunication channels. Whenever there is a conflict between the twoconstraints the first rule takes precedence over the second.These constraints ensure that this model will always find a bounded memoryschedule if one exists for the given graph. By restricting the type of dataflow actors tothose that have predictable token consumption and production patterns, it becomespossible to perform static, off-line scheduling and to bound the memory required toimplement the communication channel buffers.Computation graphs [3] are a model of parallel computation similar to processnetworks in which the model is depicted by a directed graph consisting of nodes and arcsbetween these nodes. Each node has a single valued function associated with it and eacharc has a single source and sink node at each end, which populate or remove data fromthe arc correspondingly. The source and sink functions are also termed as Producer andConsumer nodes. In this graph, each arc has a set of parameters associated with it, whichhave the following interpretation,a) AP – The number of tokens that are initially present on the arc.b) Up – The number of tokens that are added to the arc when the source functionexecutes.c) Wp – The number of tokens removed from the arc