A concurrency method: an implementation on a 3B2 network
John E. Morrell · K-State Research Exchange (Kansas State University) · 1986
Table ofFiguresiii 1 .Redundant memory accesses may also slow down the processing of a sequential program.Most sequential languages force the system to do one calculation, store the result, do the next calculation, retrieve the first calcu- lation, do some calculation with the first and second results, then store the result of this calculation and so on.This same process may be repeated over and over in a sequential program on a computer of standard architec- ture.The desirability of the concurrent processing of programs can be noted in the development of virtual CPU or multiprogramming computers [Haber- man 1976].Attempts have been made to make a sequential processing com- puter with one CPU appear to be a computer with several CPUs.Each user may be given a time-slice of an overall CPU cycle in which that user's pro- gram has access to the real CPU.The response time may be so quick, that it may appear that the user has has his own personal CPU.A system which supports this type of concurrency is still based on the same sequential pro- cessing techniques discussed previously.The response time in such a system can be slowed immensely if a large number of users are trying to access the CPU.As response time slows the appearance of a virtual CPU will decrease with a longer wait between acceptance of statements to be executed.The modern "concurrent" programming language is usually based on some sequential programming language which is modified to give the appearance of concurrent processing.These modifications tend to make the language more complex than its sequential predecessor.The user must now be careful to ensure mutual exclusion in memory accesses during processing.These languages are still processed on sequential processing computers with virtual CPUs assigned to various "concurrent" processes.Each process must -2-wait for its time-slice before it gains access to the CPU and can be executed.More and more tasks in today's society require quick processing of large and difficult operations.The need for methods and machines which allow true concurrent processing is great.Parallel processing would speed up pro- cessing operations allowing tasks to be completed more quickly.Concurrent processing could free the user from maintaining mutual exclusion in memory accesses and from specifying the sequence in which statements are to be executed.Many computer architectures and models have been put forth in an attempt to gain the advantages of concurrent processing and processing in distributed systems.Some of these architectures and models are discussed in Chapter 2. One of these models is A Concurrency Method (ACM) [Unger 1978].Chapter 3 deals with the underlying concepts of ACM: data-driven processing, single-assignment of variables and data flow principles.Also discussed are the component parts of ACM: requests, actions and stimulating/terminating conditions.Kansas State University does not have a computer designed for the type of concurrent processing needed for a desirable implementation of ACM.Such a computer would contain within one unit, multiple CPU's.Several machines of this type have been proposed but none is available yet commercially [Killmon 1985], [Kleinrock 1985], [Chang 1985], [Hindin 1985].The AT&T 3B2-300 network of microcomputers networked together with an Ethernet interface provides the type of concurrent processing needed for this implementation.In addition, it is the environment in which an office information system might reside, thus providing a test environment to sup- port other related work at the University.The physical characteristics of -3-this hardware-software environment will be discussed in Chapter 4.Chapter 5 deals with the architecture of ACM, the modules imple- mented and the structure of the request representation.Finally, some results and conclusions from this effort are presented in Chapter 6.-4-2.Machine Architectures and Models for Concurrency Research in computer architecture and design has led to several diver- gent paths of internal structures for the fast, efficient processing of data.Current studies in the area have developed such technologies as Reduced Instruction Set Computers (RISC) [Hindin 1985], Single Instruction stream -Multiple Data stream (SIMD) computers and Multiple Instruction stream -Multiple Data stream (MIMD) computers [Chang 1985] [Kleinrock 1985].Both Brinch-Hansen's "Distributed Processes" (DP) and Hoare's "Communicating Sequential Processes" (CSP) chose the process as the fundamental unit of their proposed languages.In CSP a process P sends a message to process Q by executing a statement in the form Q I action(x) { send the message to process Q } Process Q receives the message by including in the process body a command like P ?action(y) { get the message from process P } Both process Q and process P may execute their respective process state-ments in parallel until one of the processes tries to execute either the send or get statements in their process bodies.One process must wait for another process to be ready to receive or send a message.This means that one pro- cess may have to wait for the second process to reach its corresponding communication command.After the communication has been sent/received