COMMUNICATION AND PROTOCOL SATISFACTION IN ERASMUS

Over the last few years, the major chip manufactures have shifted from single core towards multicore architectures, because they realized the difficulties of increasing the clock speed of processors. The spread of multicore architectures have a pervasive effect on the performance of software. In the past, application programs would effectively speed up by itself over time, but this free ride is over. With the advent of multicore processors, enhancement in the performance of applications depends upon making effective use of hardware parallelism. As a result, parallel programming has suddenly become relevant for all computer systems. Unfortunately, parallel programming is very hard. Instead of doing everything in a sequential fashion, programmers need to ensure that their programs are designed in a way that is able to do many tasks simultaneously. As an example, in a computer game, one can’t just put every game character in a separate process, running on different CPUs. What if one processor is a little faster than another, resulting in one game character moving faster than another? Somehow programmers have to ensure that all the elements of their game are synchronized, even if they are running on different threads, across multiple cores. Programming languages can make it much easier for developers to write error free parallel programs. But the problem is that most mainstream languages do not provide suitable abstractions for expressing and controlling concurrency. Specifically, object oriented programming languages, the currently dominant paradigm, which provide concurrency through multi-threading. Object oriented programming languages are already very complex. For instance, Java provides fourteen different ways of controlling access to a variable. Adding concurrency to that makes it even harder for programmers to keep track of all concurrency issues such as shared variables, critical regions control, data races, and . . . . The primary parallel programming language with a strong and safe support for concurrency is the Occam that is based on Tony Hoare’s CSP (Communicating Sequential Processes). CSP is a process calculi that fully specifies process synchronization by mathematical notations. Despite its simple formalism, CSP turned out to be hard to implement efficiently. Several programming languages based on CSP appeared quickly, but they placed various restrictions on communication protocols in order to make the implementation efficient. This thesis contributes to the Erasmus project. A process oriented programming language that aims at making the CSP paradigm more practical. Erasmus addresses concurrency by providing processes as the primary abstraction. Processes interact with one another through synchronous channels. Channels and processes are associated with protocols that specify the interprocess communication pattern. In this thesis we focus our attention on two problems. First, the efficient implementation of the CSP generalized alternative construct that allows a process to non-deterministically choose between several possible communication. Second, the design and implementation of protocol satisfaction that allows the Erasmus compiler to statically check the safety of interprocess communication, and hence the safety of a program