rob@idacom.uucp (Rob Chapman) (09/26/90)
>The question should not be "how do we get parallelism _despite_ FORTH's >stack?"; it should be "How best can we use the power of the stack to implement >multiprocessing?". Stacks are best left attached to one processor due to there uniflow nature. >As far as I can see, the main problem in parallelism is the efficient >communication of data and instructions between processors. Stacks are an >efficient way of passing data between words (tasks, subroutines, whatever); >perhaps there's some way of passing data and/or instructions between processors >using stacks. The natural complement to stacks (LIFOs) in Forth, are queues (FIFOs). These may be used for efficient communication between processors. > ...... I'm mostly interested > in Forth as a virtual machine for data flow architecture (does anybody > talk about this anymore?) and multiprocessor architectures. > Queues are useful for containing a segment of data flow and providing elasticity between processes (or processors) in a real-time data flow architecture. I use stacks for local activity and queues for passing data (or instructions) between processes. While there are many queues used in data flow, one queue feeds the program counter (control flow). It is called the peasantq. botForth's QUIT loop is BEGIN peasantq Q> EXECUTE AGAIN Code to be run is assigned to the peasantq with ' . ' something peasantq >Q These can come from interrupts or from "peasant" code when it is executed from the peasantq. Polling words simply assign themselves back to the peasantq. Initially, in software, it took 5us on the RTX to write to the peasantq (this included error checking and interrupt masking). We reimplemented the peasantq as a hardware FIFO hanging off the GIO bus and it now takes 100ns to access it (overflow is connected to NMI). Leaping back to the main thread; it would be very easy to interconnect RTXs with up to 8 FIFOs hanging off the GIO bus, to form a very efficient data flow as well as control flow architecture. Rob
rvn@forth.mlb.semi.harris.com (Rick VanNorman) (09/27/90)
In <1990Sep26.084008.8616@idacom.uucp>, rob@idacom.uucp (Rob Chapman) writes: >>The question should not be "how do we get parallelism _despite_ FORTH's >>stack?"; it should be "How best can we use the power of the stack to >>implement multiprocessing?". > >Stacks are best left attached to one processor due to there uniflow nature. One of the techiques that I played with three years ago on the Novix (with _external_ stacks!) was connecting two processors' stacks via dual-port memory, but with one processor's addresses inverted such that the address map of the stacks looked like: processor 1 processor 2 stack stack 0 255 1 254 ... ... 254 1 255 0 Thus processor one could push numbers onto the stack and feed processor 2. We never did much with this, or find anywhere it could really be useful -- but it was an interesting (thought) experiment. Could this be useful? Would it justify placing the stacks of a Forth engine off-chip again? (they are on-chip for speed and pin-count reasons, wiggling pins with CMOS drivers at 10MHz is _slow_ compared to having memory on the chip) Rick VanNorman Staff Engineer, Software Development RTX Marketing Harris Semiconductor Melbourne, Florida, USA All opinions expressed by me, real or otherwise, are my own.
dwp@willett.pgh.pa.us (Doug Philips) (10/04/90)
In <1990Sep26.084008.8616@idacom.uucp>, rob@idacom.uucp (Rob Chapman) writes: [I don't remember any longer who the '> >' should attributed to. -dwp] > >As far as I can see, the main problem in parallelism is the efficient > >communication of data and instructions between processors. Stacks are an > >efficient way of passing data between words (tasks, subroutines, whatever); > >perhaps there's some way of passing data and/or instructions between processors > >using stacks. > > The natural complement to stacks (LIFOs) in Forth, are queues (FIFOs). > These may be used for efficient communication between processors. I think the issue of efficiency is a red herring here. The reason that stacks are so wonderful for a single thread of execution is because words run time behaviour "nests" in a way that stacks support (or visa versa). If you want to do co-routines or lightweight processes in Forth or even multi-user Forth, each thread/user must get its own stack, user variables, etc. I would suspect that there would be a direct mapping of useful techniques from multiple process/user Forth implementations into Multiple processor/process/user Forth implementations. I think the stack paradigm that makes Forth a powerful single threaded language is just not suitable for a multiprocess environment. I think Rob's queues are an interesting idea. Message Passing systems typically use that paradigm. I would suggest that the philosophy of Forth's stack is not directly applicable, but is applicable in kind. The thing to choose will be to multiprocess(or) Forth what stacks are to single process Forth. -Doug --- Preferred: dwp@willett.pgh.pa.us Ok: {pitt,sei,uunet}!willett!dwp