Control System Model for Critically Timed Sources
R. Parchmann · Journal of the ACM · 1979
In discussing a model of a control system for cnucally umed sources Hellerman gives a necessary cond~tton for the existence of a control system and conjectures that his algorithm always leads to a control system This con3ecture Is proved here KEY WORDS AND PHRASES combmatoncs, multiplexing, data flow clrcmts, bus control cg CATEGORIES 5 39, 6 33In this paper we prove Hellerman's conjecture [1, p. 233] regarding a control system model for critically timed sources.The control system should be able to generate the gate signals to control a bus where the sequence of signals must satisfy time constraints.The bus Is a simple single bus as shown in Figure 1.The following time constraints characterize the model:(1) The time during which the connection of a source and a destination must be maintained is assumed to be constant (independent of sources and destinations).This time ~s taken as the unit time t of the system.(2) Certain sources are critical.Each critical source S, is characterized by an integer p,.The ttme constraints reqmre the tth critical source S, to be connected to the bus once in each ttme interval of length p,t(3) If a ume interval is not required for critical sources, it can be used by noncritical sources.Without loss of generality we may assume that we have only one destination.Let G(p~ ..... pn) denote a control system with n critical sources characterized by the integers p~ ..... pn.Hellerman uses a counter c: and a participation indicator g: for source S: to describe the state of a control system.In this paper we use the concept of state vectors.A state vector is a vector A = (al, ., an) of integers Each component a: denotes the number of time intervals that remain in which thejth source can be connected to the bus with respect to the ume constraints.For a control system we have 0 pj then c~ = aj -p: and gj = 1.A sequence A0, A,, .. of state vectors ~s used to describe the funcuon of a control system C,(px ..... p.).Definttion 1.A state sequence of a control system C~(p~ .... pn) is a sequence A0, A~, ... of vectors w~th (l) A0 = e = (pl ..... p,).(2) LetA, = (a~ ..... a~,).Then 0 < a~< 2p: holds forj ~ [l.n], 1 = 0, 1, 2 ....