[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: "Adrian Lawrence" <adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>*Subject*: RE: Dynamic Priority*From*: "Gerald Hilderink" <g.h.hilderink@xxxxxxxxxxxxx>*Date*: Tue, 27 Apr 1999 00:15:38 +0200*Cc*: "Occam-com mail group" <occam-com@xxxxxxxxx>*Importance*: Normal*In-reply-to*: <E10br0a-0007Yx-00@xxxxxxxxxxxxxxx>

What about this? Design (index free?) ~~~~~~~~~~~~~~~~~~~~ The expression {P0} > {P2,P3} > {P1,P4,P5} can be drawn as a undirected graph with {P0}, {P2, P3} and {P1, P4, P5} as nodes connected by arcs that are labelled by ">". This graph can also be represented by {P0} > ({P2} = {P3}) > ({P1} = {P4} = {P5}) which can be drawn as an undirected graph with {P1},..,{P5} as nodes connected by arcs that are labelled by ">" or "=". This way we could extend our existing data-flow design with priority relation arcs. I belief that indexes at this level of the conceptual design can (should) be hidden and can (should) being added later at implementation level (maybe by the compiler or scheduler). One press on the button and the PAR will be generated with indexes we do not want to know ... or do we want to know the indexes? For example, in {P0} > {P2,P3} > {P1,P4,P5} the indexes [10,1267,1267,100034,100034,100034] would be valid. I guess the indexes must be in range of the number of processes (here [0..n-1] with n = 6). General Ordered Relation ~~~~~~~~~~~~~~~~~~~~~~~~ A priority is a precedence relation between processes in terms of greater than ">" or equal to "=". The relations ">" or "=" between processes can be added to the design by some reasons of timing constraints or precedence constraints. As long as the relation is valid I do not want to know the indexes. I belief, this is conceptual and that makes reasoning about precedence relations (or priorities) much simpler. The compiler or scheduler can do the hard work. Say, pri(Pi) is the priority of Pi and index(Pi) is the index of Pi in the PAR construct. pri(P1) > pri(P2) means that P1 has a higher priority as P2. Or pri(P1) > pri(P3) is equal to index(P1) < index(P2), which means the index of P1 is lower than the index of P2. index(P1) < index(P2) is equal to index(P1) = index(P2) - x, where x > 0 (x does not always have to be 1). We could generate our priority indexes by some algorithm. The indexes can be anything that fits the scheduler implementation as long as the priority relations maintain valid. PAR and PRI PAR ~~~~~~~~~~~~~~~ Let P1 and P2 be concurrent processes, then pri(P1) > pri(P2) is PRI PAR P1 P2 pri(P1) = pri(P2) is PAR P1 P2 pri(P1) > pri(pri(P2) = pri(p3)) is the nested composition PRI PAR P1 PAR P2 P3 The distinct compositions PRI PAR and PAR are very useful in this matter. However, this may also correspond to PAR (CHAN OF [x, x+y, x+y]) with x >= 0 and y > 0. P1 P2 P3 where we need to know x and y. With our scheduler approach we create a new dispatcher process for each PRI PAR constructs. The dispatcher manages the ready queue and running queue. Processes in the PRI PAR construct will be assigned to different ready queues represented by an 8-bits word. Processes in a PAR construct will be assigned to the same ready queue of the parent dispatcher. It's simple, fast and static. Again, the distinct compositions PRI PAR and PAR are very useful in this matter. Gerald. -----Original Message----- From: Adrian Lawrence [mailto:adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx] Sent: maandag 26 april 1999 21:26 To: occam-com@xxxxxxxxx Subject: Dynamic Priority Dynamic Priority ~~~~~~~~~~~~~~~~ Starting from existing occam, we may as well leave PAR as it is. Although HARD PAR or SOFT PAR or TRANSPARENT PAR or PAR(HARD) may be needed. But we can have an optional CHAN parameter in PRI PAR: I think that this is the more accurate representation. PRI PAR(CHAN OF something priority) P0 P1 ... PN Specifying the POR (Partial Order Relation) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The syntax gives a reference order. My original idea of sending the ordered image of a bijection as a table of indices is simple, and I hope lightweight for the sender to prepare, and for the implementation to utilize. It is pretty much a preprepared lookup table of offsets. Gerald raises the idea of a more general order relation. Do we need this? Will it ever be needed? Anyway, one more general possibility is to have a list of ordered sets: S0 > S! > S2.... For example {P0} > {P2,P3} > {P1,P4,P5} would correspond to PRI PAR P0 PAR P2 P3 PAR P1 P4 P5 . Since each set Si could be represented by a bit list, this could be sent as bit arrays (packed into INTs I guess, with a restriction of bits_in_word, in a given set). Of course, if we ever have real BIT arrays as I suggested a few years ago, this is another application. :-) So above would be specified as 00000001,00001100,00110010 in 8-bit words. No doubt there are many ways to do this, and perhaps we could define specific protocols to encode them. But do we need any of this? Adrian -- A E Lawrence, MA., DPhil. adrian.lawrence@xxxxxxxxxxxxxx MicroProcessor Unit, 13, Banbury Road, Oxford. OX2 6NN. UK. Voice: (+44)-1865-273274, Fax: (+44)-1865-273275

**Follow-Ups**:**RE: Dynamic Priority***From:*Oyvind Teig

**References**:**Dynamic Priority***From:*Adrian Lawrence

- Prev by Date:
**Re: Is PRI PAR useful for hardware?** - Next by Date:
**Re: Is PRI PAR useful for hardware?** - Previous by thread:
**Dynamic Priority** - Next by thread:
**RE: Dynamic Priority** - Index(es):