Process It
Resume:
To Appear in the Proceedings of **th ACM/IEEE International Conference on Parallel Architectures and Compilation Techniques (PACT 2004)
Fast Paths in Concurrent Programs
Wen Xu Sanjeev Kumar Kai Li
Department of Computer Science Intel Labs Department of Computer Science
Princeton University Intel Corporation Princeton University
***@**.*********.*** *******.*****@*****.*** **@**.*********.***
ABSTRACT
Compiling concurrent programs to run on a sequential pro-
(b) Multiprocessor
P1 P1
(a) Uniprocessor
cessor presents a di cult tradeo between execution time
and size of generated code. On one hand, the process-based
approach to compilation generates reasonable sized code but P2 P2
P3 P3
incurs signi cant execution overhead due to concurrency.
On the other hand, the automata-based approach incurs a P4 P5 P4 P5
much smaller execution overhead but can result in code that
is several orders of magnitude larger.
This paper proposes a way of combining the two approaches
so that the performance of the automata-based approach can
Figure 1: Concurrent Program
be achieved without su ering the code size increase due to
it. The key insight is that the best of the two approaches
can be achieved by using symbolic execution (similar to the
proach (Section 4). The two approaches di er radically in
automata-based approach) to generate code for the com-
the concurrency overhead and the size of the generated code.
monly executed paths (referred to as fast paths) and using
A study [15] evaluated the two approaches on a set of con-
the process-based approach to generate code for the rest of
current programs written in Esterel [6]. The study found
the program. We demonstrate the e ectiveness of this ap-
that the automata-based approach resulted in code that was
proach by implementing our techniques in the ESP compiler
twice as fast as the process-based approach. However, the
and applying them to a set of lter programs and to VMMC
size of the code generated by the automata-based approach
network rmware.
was 2 3 orders of magnitude larger than that produced by
the process-based approach.
1. INTRODUCTION This paper proposes a technique for extracting and op-
Concurrency is a convenient way of structuring timizing fast paths from concurrent programs so that the
programs [19, 24] in a variety of domains including embed- performance bene t of the automata-based approach can
ded devices [6, 17], user interfaces [10, 31], programmable be achieved without signi cantly increasing the size of the
devices [21], servers [32], media-processing applications [20], generated code. A fast path is a commonly executed path
and network software stack [4, 29]. This is often true even in a program. Substantial performance improvements can
when these programs are written to run on a single proces- be achieved by aggressively optimizing the fast paths in the
sor. This is because programs in these domains are required programs. Past research [30, 26, 23] has focused on fast
to simultaneously process multiple external events at the paths in sequential programs.
same time. Concurrent programs have multiple threads of In the absence of automatic fast path extraction, fast
control that coordinate with each other to perform a single paths are often implemented manually by the programmer [21].
task. The multiple threads of control provide a convenient The programmer can insert a predicate in the program to
way of keeping track of multiple contexts in the program. check for the common case and transfer control to the fast
Figure 1 shows a concurrent program with 5 concurrent path code. The fast path code has to be functionally equiv-
threads of control (P1-P5). On a uniprocessor, the entire alent to the corresponding path in the program. The pro-
concurrent program needs to be compiled to run e ciently grammer is responsible for manually extracting and optimiz-
on a single processor. On a multiprocessor (with 2 proces- ing the fast path code.
sors), the program is partitioned so that P1-P3 are run on Although, manually extracting fast paths often results in
the rst processor while the remaining program is run on good performance, it su ers from three drawbacks. First,
the second processor. In each case, several threads of con- manually extracting fast paths involves substantial program-
trol have to be compiled to e ciently run on a sequential mer e ort. Second, manually implementing fast paths is
processor. This paper addresses this problem. very error prone. Fast paths violate abstraction boundaries
The overhead of implementing concurrency on sequen- and rely on global information like the state of the di erent
tial processors can be substantial. There are two main ap- threads of control and their local data structures. As the
proaches to compiling concurrent programs on sequential program evolves, for each change made to the concurrent
processors: process-based approach and automata-based ap- program, a corresponding change has to be made to the fast
To Appear in the Proceedings of 13th ACM/IEEE International Conference on Parallel Architectures and Compilation Techniques (PACT 2004)
path. In addition, programmers often introduce subtle bugs
when they try to aggressively optimize fast paths. Third,
it is di cult to build robust fast paths. One often ends
up with fast paths that help simple applications with very
predictable process interactions but have little impact on ap-
channel hostSendRequestC( int, int ) external out;
1:
plications. The more speci c the fast path predicate (that channel hostFetchRequestC( int ) external out;
2:
identi es the fast path), the more specialized and e cient channel translateRequestC( int, int );
3:
fast path will be. However, it also means that the predicate channel translateReplyC( int, int );
4:
will be satis ed less often. It is easier to experiment with channel dataSendC( int, int );
5:
channel networkSendC( int ) external in;
6:
various fast paths and identify the right one to employ if the
7:
programmer e ort needed to build a fast path is small.
process hostRequest {
8:
var virtualAddress, physicalAddress, size, source;
9:
Summary of Contributions. This paper presents tech- while (true) {
10:
niques to automatically generate fast paths in concurrent alt {
11:
in( hostSendRequestC, virtualAddress, size) {
12:
programs using a compiler. This approach avoids the draw-
out( translateRequestC, virtualAddress, size);
13:
backs associated with manual fast path extraction while pro-
while ( true) {
14:
viding the performance bene ts. The main contributions of in( translateReplyC, physicalAddress, size);
15:
this paper are the following: if ( size == 0)
16: break;
out( dataSendC, physicalAddress, size);
17:
1. It extends the traditional de nition of fast paths to
} // while
18:
make them more exible (Section 2.2).
19: #1
2. It proposes a variant of path expressions that not only } // in
20:
allows the programmer to specify fast paths in concur- in( hostFetchRequestC, source) {
21:
rent programs but also lets them specify the scheduling // Code omitted
22:
choices made on the fast path. A key feature of the fast } // in
23:
} // alt
24:
path speci cations is that they are just hints while
} // while
25:
they improve the performance of the program, they do
26: }
not change the semantics of the program and, there- 27:
fore, do not a ect program correctness. (Section 3) process translateAddress {
28:
3. It presents a technique for extracting and optimizing constant pageSize = 4096;
29:
fast paths in concurrent programs. This technique var virtualAddress, physicalAddress, size;
30:
while (true) {
31:
delivers the performance of the automata-based ap-
in( translateRequestC, virtualAddress, size);
32:
proach without the associated blowup in the size of
assert( virtualAddress % pageSize == 0);
33:
the generated program. One important aspect of this assert( size % pageSize == 0);
34:
technique is that it preserves the fairness guarantees while ( size > 0) {
35:
of the program. (Section 4) if ( translationUnavailable(virtualAddress)) { #2
36:
4. It provides a practical demonstration of the approach // Code to f etch the translation entry
37:
} // if
38:
by implementing the techniques described in the con-
39: physicalAddress = translate( virtualAddress);
text of the ESP [21] compiler. A set of lter programs
out( translateReplyC, physicalAddress, pageSize);
40:
and VMMC network rmware are used to evaluate the 41: size = size - pageSize;
e ectiveness of the technique. On lter programs, our } // while
42:
technique outperforms even the automata-based ap- out( translateReplyC, 0, 0); // Done
43:
proach without any dramatic increase in the size of the } // while
44:
45: }
generated code. On VMMC rmware, our technique
46:
achieves up to 22% improvement in latency and up to
process networkSend {
47:
40% improvement in bandwidth over the process-based var physicalAddress, size, packet;
48:
approach. (Section 6) while (true) {
49:
in( dataSendC, physicalAddress, size);
50:
51: packet = preparePacket( physicalAddress, size);
2. PROBLEM STATEMENT out( networkSendC, packet); #3
52:
} // while
53:
This paper presents a technique to reduce the concurrency
54: }
overhead in concurrent programs by extracting and aggres-
sively optimizing fast path code. This section starts with a
Note: The assert statements in the code are used to state
description of a simple concurrent language and an example
the assumptions made to simplify the example. The #1 and
that is used throughout this paper. It then describes fast
#2 are annotations to mark statements and are used in
paths in detail. Finally, it discusses the scope of the paper.
Section 3.
2.1 Concurrent Programs
In this section, we describe a simple concurrent program-
Figure 2: A Running Example. (Illustrated in Figure 3)
ming language that we use to demonstrate the techniques
presented in this paper.
In this language, concurrency is expressed using processes
and channels. A program consists of a set of processes com-
municating with each other over channels. Each process
To Appear in the Proceedings of 13th ACM/IEEE International Conference on Parallel Architectures and Compilation Techniques (PACT 2004)
C2 Modular Concurrent
C1
C1
Program Fast Paths
C3
P1 P2
Common Case
P1 C2 P2
C4
C5
C3 C4
Process Abort
P3
Channel Normal Exit
P3 P4
External Channel
C6
C5 C6
Process
Figure 3: Example. Illustration of the example in Fig- Channel
ure 2. Process P1 is hostRequest, P2 is translateAddress,
and P3 is networkSend. Channel C1 is hostSendRequestC, External Channel
C2 is hostFetchRequestC, C3 is translateRequestC,
C4 is translateReplyC, C5 is dataSendC, and C6 is
networkSendC. Figure 4: Fast Paths in Concurrent Programs
represents a sequential ow of control in the concurrent pro- Figure 2 and Figure 3 show a code fragment that is used
gram. as a running example in this paper. It is extracted from
Processes communicate with each other over channels. our VMMC rmware code [21] for a gigabit network card.
Messages are sent over the channels using the out opera- The code shows the steps involved in sending a packet in
tion and received using the in operation. Communication the VMMC rmware [21]. When the user application has
over channels is synchronous1 or unbu ered a process has some data to send, it sends a request via channel host-
to be attempting to perform an out operation on a channel SendRequestC to process hostRequest. After process hostRe-
concurrently with another process attempting to perform an quest gets the request, it rst translates the virtual address
in operation on that channel before the message can be suc- to physical address, and then sends the data page by page to
cessfully transferred over the channel. Consequently, both in the destination. Process hostRequest consults process trans-
and out are blocking operations. The alt statement allows a lateAddress for address translation. Process translateAd-
process to wait on in and out operations on several di erent dress has a table which caches recently translated addresses.
channels till one of them becomes ready to complete. On a table hit, the physical address is immediately avail-
External channels allow the concurrent program to com- able. Otherwise it needs to fetch corresponding translation.
municate with external world (for instance, to send a packet For messages more than one page, process translateAddress
into the network). External channels are like regular chan- returns the physical address for each page. Then process
nels; the only di erence is that they have an external reader hostRequest makes a request to process networkSend to ac-
or a writer. tually send the page onto the network.
In the presence of nondeterminism (due to the alt state-
ment), the language guarantees fairness.2 When multiple
2.2 Fast Paths
channel operations are ready in an alt, if the implemen-
A path [26, 3] is a dynamic execution path in a program.
tation always chooses one particular channel operation, the
Typically, a small set of paths in the program account for a
processes waiting on the other channels can be starved out.
large percentage of its execution time.
This is referred to as unfairness. Fairness, therefore, implies
A fast path provides better performance to a set of com-
freedom from starvation. It should be noted that fairness
monly executing paths in the program. It should be empha-
does not imply that each of the enabled guarded statements
sized that a fast path is not necessarily a single execution
will be chosen with equal probability.3
path in the program. A fast path is typically a set of related
In additional to channel operations, the language supports
execution paths in the program.
the common control ow statements like if-then-else and
Traditionally, a fast path [30, 26, 23] consists of two com-
while statements. For simplicity, it supports just one type
ponents: A predicate that identi es a common case, and
of data: integers.
specialized code that is optimized to e ciently handle that
common case. As long as the predicate holds, executing the
1
Also known as rendezvous channels.
specialized code is functionally equivalent to the original ex-
2
Two types of fairness guarantees can be provided: weak
ecution path chosen without the fast path. It is formed by
fairness and strong fairness [2]. However, the fast path
extraction technique described in this paper preserves the extracting code fragments from several di erent modules.
fairness semantics for both these types. Consequently, we This allows fast paths to avoid module-crossing overheads;
do not make a distinction between the two in the rest of it also makes them more amenable to compiler optimiza-
this paper.
tions.
3
The term fairness is sometimes used in the operating
In this paper, we extend the traditional notion of a fast
systems community to imply this meaning. In this paper,
path to allow them to abort midway through the execution
we always use the term fairness to only imply starvation-
freedom. (Figure 4) for two reasons. First, it is often di cult to iso-
To Appear in the Proceedings of 13th ACM/IEEE International Conference on Parallel Architectures and Compilation Techniques (PACT 2004)
late the fast path with a single predicate that has to hold fastpath demo {
at the start of the fast path. Second, in some cases, a pred- process hostRequest {
icate might not hold at the start of the fast path but might statement hostSendRequestC as H0,
become true later. For instance, a DMA engine4 might not translateRequestC as H1
translateReplyC as H2,
be available at the start of the fast path but might become
dataSendC as H3,
available by the time it is needed at a later point on the fast #1;
path. start H0 ? (size
follows H1 ( H2 H3 )* ;
2.3 Scope exit #1;
}
To extract fast paths from programs, three questions need
process translateAddress {
to be answered.
statement translateRequestC as T1, #2;
1. How are fast paths selected? This requires knowledge start T1 H1;
about which paths in the program are critical as well exit T1;
as commonly executed. }
process networkSend {
2. How does the programmer specify the fast paths in
statement dataSendC, #3;
the program? The compiler will use this information
start dataSendC;
to aggressively optimize the fast path.
exit #3;
3. How does the compiler extract and optimize the fast }
path? }
In this paper, we address the last two questions: specify-
ing and optimizing fast paths. Identifying fast paths is an Note: #1, #2, and #3 name the rst statement after
independent problem that is not addressed here. In this pa- the point where they appear. The ? is used to specify a
per, we assume that the programmer identi es the fast paths predicate that has to hold at the statement. The
either based on knowledge of the application behavior or by is used to specify the statement in the other process with
using some recent work on path pro ling in sequential [3, 22] which it is communicating. The as allows the programmer
and parallel programs [11, 31]. The work presented in this to specify a shorter name for a statement.
paper can also simplify the task of identifying fast paths.
This is because a programmer (or even an automated tool)
can try out several di erent fast paths with little e ort to Figure 5: A Fast Path Example.
determine the most pro table fast path.
3. SPECIFYING FAST PATHS erful way of expressing control ow in programs and have
been widely used (Section 7).
Traditionally, fast paths in sequential programs are often
We will now illustrate our fast path speci cation language
speci ed by annotating the program to indicate the likely
with a fast path (Figure 5) in our example (Figure 2). Four
result (true or false) of conditional statements of the pro-
elds can be speci ed for each process involved in the fast
gram [27]. The HIPPCO [11] compiler allows a probability
path. The statement eld enumerates the list of all state-
to be speci ed for conditional statements. These probabil-
ments that are relevant to the fast path. The start eld
ities can be determined by program pro ling. Another ap-
speci es the starting statement element while the exit eld
proach [23] is to use a predicate to specify fast paths. The
speci es the statement element that marks the end of the
compiler then extracts the fast path code by partially eval-
fast path in that process. The follows eld is a regular
uating the code based on the predicate. Neither of these
expression on statement elements that speci es the set of
approaches meets our needs.
execution paths that the process can take between start
To specify fast paths in concurrent programs, we identi ed
and exit. The fast path is terminated if either the exit
three desirable properties that the fast path speci cation
element is satis ed or if it deviates from the path speci ed
mechanism should satisfy. First, the fast path speci cation
by the follows eld.
should be just hints to the compiler and, therefore, should
Three points are worth noting here. First, the follows
not a ect the correctness of the program. In addition, since
and exit elds are optional. Second, any statement that
they are just hints, the fast path speci cation should be
is not explicitly included in the statement eld has no im-
kept separate from the code to the extent possible. This
pact on whether or not an execution path is selected on the
would ensure that the speci cations do not make the code
fast path. This helps to keep the regular expression small.
less readable by cluttering it. Second, the fast paths should
For instance, in process translateAddress, the fast path is
have the ability to abort prematurely (Section 2.2). Finally,
aborted if it encounters statement #2 (Figure 5). However,
the speci cation should allow programmer to control the
statements involving operations on channel translateReplyC
scheduling of the di erent processes involved in the fast path
are simply ignored while determining if a particular path be-
since it can have a big impact on the performance. Note
longs to the fast path because it is not listed in the statement
that the traditional approaches described in the previous
eld. Third, the exit eld is redundant in process networkSend
paragraph do not satisfy these properties.
(Figure 5). This is because it speci es a null path expres-
This paper proposes using an extension of path expres-
sion for the follows eld. Consequently, the fast path would
sions [9, 8] to specify fast paths in concurrent programs. A
terminate if it encountered either of dataSendC or #3 af-
path expression is a regular expression over control points
ter starting the fast path as it would no longer satisfy the
in a program. Path expressions provide a succinct and pow-
follows eld.
4
A DMA engine allows a device to move bulk data e ciently. A statement element is the basic unit in the fast path
To Appear in the Proceedings of 13th ACM/IEEE International Conference on Parallel Architectures and Compilation Techniques (PACT 2004)
speci cation. In the simplest case, a statement element is The process-based approach [28, 15, 21] is the popular ap-
just a statement.5 A statement element can also qualify a proach to compile concurrent programs to run on sequen-
statement with one or more of the following. First, a predi- tial processors. In the process-based approach, the compiler
cate can be speci ed that has to hold at that statement. For generates the code for each process separately and inserts
example, the start condition in process hostRequest speci- additional code to periodically context switch between them
es that the predicate size ). Finally, it can explicitly specify the roughly the sum of the sizes of the individual processes.
scheduling decisions on the fast path and override the de- However, the generated code incurs a runtime overhead due
fault scheduling policy. to the concurrency. The runtime overhead stems from three
Our default scheduling policy works as follows: At the sources. First, a context switch involves saving the state of
start, all processes on the fast path that are ready to run the running process, and then retrieving the state of the next
(i.e. unblocked) are placed in a FIFO ready queue (in the process and running it. Second, when values are transferred
order the processes appear in the fast path speci cation). over a channel, there is overhead associated with it that is
The execution begins with the rst process on the queue similar to the overhead of passing parameters to a function.
and proceeds until a channel operation is encountered. If the Finally, nondeterministic statements require a mechanism
channel operation causes it to block, the next process from (like randomly picking between the available options) that
the ready queue is picked and executed. Alternately, if the guarantees fairness.
currently executing process communicates with a blocked The automata-based approach [10, 6, 12, 29] is a radically
process that is part of the fast path, the process performing di erent approach that uses symbolic execution to generate
the in (read) operation is the one that continues while the code for concurrent programs. Symbolic execution is a gen-
other process is added to the ready list. eral technique that has been applied in wide variety of areas
The default scheduling policy works well in practice be- including program testing, model checking, program anal-
cause it often re ects the critical path in the concurrent ysis, and optimization. In the automata-based approach,
program. For instance, the default policy picks the best symbolic execution is used to enumerate the control state
scheduling for the example in Figure 2 (which was extracted space of a concurrent program. We explain this brie y in
from a real program [21]). In addition, copy propagation op- the following paragraph (See [29] for a detailed description).
timization is very e ective with this policy because the pro- The automata-based approach essentially treats each pro-
cess reading from the channel is likely to use those values cess in the concurrent program as a state machine and com-
immediately. bines all the state machines in the program to generate a
In a few rare cases, di erent scheduling decisions (from single global state machine. Each statement in a process
the ones made by the default scheduling policy) at a few represents a state in the corresponding state machine. A
locations on the fast path can improve performance. We tuple consisting of the state of each of the various state ma-
provide a simple yet powerful mechanism to override the de- chines denotes a state of the global state machine. At each
fault scheduling decision. An element can be quali ed with step, the global state machine takes a state in one of the in-
a yield directive that allows the currently scheduled process dividual state machines. This is repeated until all the transi-
to specify a di erent process to be scheduled immediately. tions reachable from the start space are explored. It should
For instance, suppose (H2 yield translateAddress) were be noted that the nondeterminism in various processes of
used in the place of H2 in the follows eld of process the concurrent program gets translated into nondetermin-
hostRequest. In this case, after the communication on istic transitions in the global state machine. Consequently,
channel translateReplyC, process translateAddress would the global state machine is essentially a sequential program
be scheduled to run instead of process hostRequest. with nondeterminism.
The advantage of the automata-based approach is that
there are no context switches and channel operations in the
4. GENERATING FAST PATHS generated code. Although, there is still overhead involved
due to the nondeterminism, the code generated is extremely
4.1 Background fast. The disadvantage of this approach is that the global
state machine generated can be, in the worst-case, expo-
This paper focuses on the application domains that use
nential in the size of the individual state machines. Some
concurrency as a convenient way to structure programs even
optimization techniques [12, 11] alleviate the code blowup
on a uniprocessor (Section 1). Consequently, the most e -
problem by identifying and eliminating some of the dupli-
cient way to execute these programs is to run all its processes
cated code. Still, the code blowup remains exponential in
in the same virtual address space (i.e. single operating sys-
the worst-case.
tem process) and perform scheduling at the user level in
Edwards et al. [15] compared the two approaches on a set
the runtime system. There are two main approaches to im-
of Esterel programs. Esterel (Section 7) is a deterministic
plement this: process-based approach and automata-based
concurrent language. The study found that the automata-
approach.
based approach resulted in code that was twice as fast as
the process-based approach. However, the size of the code
5
Statements in a process are identi ed either using a chan-
generated by the automata-based approach was 2 3 orders
nel name (when the channel name uniquely identi es a
statement that performing an operation on it) or using of magnitude larger than that produced by the process-based
the # annotation. For instance, the #2 refers to the approach. Such a large increase in the size of generated code
rst statement in the body of the if statement in process is often unacceptable.
translateAddress.
To Appear in the Proceedings of 13th ACM/IEEE International Conference on Parallel Architectures and Compilation Techniques (PACT 2004)
4.2 Extracting Fast Paths
This paper proposes combining the two approaches so
that the generated code achieves the performance of the
automata-based approach while resulting in code size sim-
ilar to that from the process-based approach. The key in-
sight is that the best of the two approaches can be achieved
by using symbolic execution (similar to the automata-based
approach) to generate code for the fast paths and using the
process-based approach to generate code for the rest of the
concurrent code.
Our approach proposes generating code for the concurrent
program in three stages:
1. Process-based Baseline Code. The compiler uses
process-based approach to generate code for the program.
This portion of the code is a complete stand-alone imple-
mentation of the program.
2. Extracting Fast Path Code. The compiler uses the
fast path speci cation to generate code for the fast paths.
For each fast path speci ed, the compiler rst translates the
path expressions (one for each process involved) into nite-
state machines. Each state-machine includes a start state
and a normal exit state which corresponds to the start and
the end of the fast path. Then, the compiler uses sym-
bolic execution to follow all possible execution paths from
the start of the fast path. During the symbolic execution of Figure 6: Fast Path Extraction
each execution path, the compiler makes transitions in the
corresponding state machines each time an interesting lo-
cation6 is encountered in the program. The situation when
3. Entering and Exiting Fast Path. The process-based
such a transition is not available corresponds to a path that
code and the fast path code are then combined by adding
no longer matches the fast path speci cation. When this
code that transfer control to each other (Figure 4). In
happens, the execution point (where the violation is rst
the process-based code, code is inserted at the appropri-
detected) is marked as an abort point and that execution
ate points to check if the starting condition for the fast path
path is not longer executed symbolically. Similarly, if the
is satis ed and, if it is satis ed, transfer control to the fast
state machine reaches the normal exit state, the execution
path code. In the fast path code, code is added at the exit
point is marked as a normal exit point and that execution
points (normal exit and abort points) that return control to
path is terminated.
the process-based code.
Figure 6 illustrates the symbolic execution performed to
We need to do two things when transferring control be-
extract the fast path speci ed in Figure 5 for the example
tween the process-based code and the fast path code. First,
in Figure 2 & Figure 3. Each state in this gure includes
we need to update the program counter pointer for each
the program counter (line number from Figure 2) for each
involved process, this pointer identi es which instruction in
process in the fast path. The starting state (as speci ed in
the process is being executed. Second, each process has a
Figure 5) corresponds to the state (P1=13, P2=32, P3=50).
state variable that remembers which channel operations are
At each step, one of the processes is being symbolically exe-
ready in an alt; these state variables need to be updated.
cuted. For example, at state (P1=15, P2=41, P3=50), pro-
cess P2 is chosen to be executed. It symbolically executes
4.3 Process Scheduling on the Fast Path
the statement P2.size=P2.size-pageSize on line 41 and
A fast path usually involves multiple processes. There-
changes its program counter to 35. Two processes may
fore, process scheduling decisions have to be made during
also communicate. For example, at the start state (P1=13,
symbolic execution. Since the scheduling decisions have a
P2=32, P3=50), process P1 and P2 communicate on chan-
big impact on the performance, the programmer is allowed
nel translateRequestC. Therefore the two processes update
to precisely specify the scheduling decisions to be made on
their program counter and the executions enters the next
the fast path (Section 3).
state (P1=15, P2=35, P3=50). Any state in which one of
Our compiler uses the speci ed scheduling policy during
the processes has reached an end state or deviated from the
fast path extraction. As the start of the fast path, it puts
speci ed path is marked as an exit state or an abort state
all the processes involved in the fast path that are ready
respectively. No transition out of such a state is considered.
to be executed (i.e. unblocked) in a ready list (FIFO) and
For example, in state (P1=19, P2=32, P3=50), process P1
starts symbolically executing the rst one (say PA ). It fol-
has reached the exit state, so the symbolic execution does
lows this process until it encounters a channel operation or a
not proceed any further on this path.
yield directive to yield to a di erent process (say PB ) (Sec-
tion 3). At this point, there are three possibilities. First,
6
Recall that the fast path speci cation speci es all locations
in the program that are relevant to it. if it (PA ) encounters a channel operation and the channel
To Appear in the Proceedings of 13th ACM/IEEE International Conference on Parallel Architectures and Compilation Techniques (PACT 2004)
operation blocks, the symbolic execution picks up the next formance of fast path code.
process (say PC ) in the ready list and symbolically executes
it. Second, if the channel operation can complete and in- Enabling Traditional Optimizations. Traditional opti-
volves communication with another process (say PD ), one mizations, like copy propagation and dead code elimination,
of the two processes PA and PD is picked to be symbolically on fast paths result in program specialization and cross-
executed next (based on the scheduling decision speci ed) module optimizations. The fast path is composed of frag-
and the other is put in the ready list. Finally, if it (PA ) ments of code extracted from several processes. Since the
encounters a yield directive, PB is extracted from the ready code is executed only when the starting condition is sat-
list to be symbolically executed while PA is put on the ready is ed, the fast path code can be specialized assuming the
list. starting conditions. In addition, since process7 boundaries
are eliminated while extracting fast paths, the optimizations
4.4 Fairness on the Fast Path on fast paths are e ectively cross-module optimizations.
However, traditional optimizations cannot be directly ap-
The generated code is required to preserve fairness se-
plied to the fast paths in isolation. This is because their
mantics of the program (Section 2). Fast path involves code
control ow is linked back to the rest of the code via the
that is extracted from di erent processes and thereby makes
abort/exit points. To solve this problem, we need to prop-
some scheduling decisions. The compiler has to ensure that
agate some information back from each of the individual
it does not introduce starvation in the program. Starvation
processes to the fast paths. For instance, we perform live-
can arise from two situations. Either the speci ed fast path
variable analysis on the fast path in two stages. First, we
can be in nitely long (due to the presence of the repetition
perform live variable analysis in each of the processes. Sec-
operator in the path expressions). This can potentially al-
ond, this liveness information is propagated to each of the
low a fast path involving two processes to starve out a third
abort/exit point in the fast path depending on where the
process. Or it arises if the nondeterminism is not handled
exit/abort point in the fast path returns control to the var-
correctly on the fast path.
ious processes. Using this information, the liveness analysis
Our compiler employs a simple strategy to handle fair-
can be performed on the fast path.
ness: it simply relies on the underlying process-based code
that already handles fairness. To avoid starvation due to the
Speeding up fast path using lazy execution. Some
in nitely long fast paths, it places a bound (by maintaining
counters for each repetition operator) on how long the fast code can be eliminated by rearranging the sequence of exe-
path can execute and aborts the fast path if the bound is ex- cution on the fast path. For example, a lot of assignments
ceeded. Then the control would be returned to the process- are done on the fast path to mimic message passing between
based code which ensures fairness. To avoid starvation due processes to update their local variables. If the fast path is
to nondeterminism, the generated code periodically chooses taken to the end, some of these assignments might not be
not to execute the fast path code even when the starting necessary and can be eliminated using copy propagation.
conditions for that fast path are satis ed. Note that this However, these assignments might be necessary if the fast
is required for only those fast paths that include a nonde- path aborts. This can be addressed by using lazy execution.
terministic choice. This means that the process-based code By delaying these assignments until the points where the
that ensures fairness is executed a fraction of the time even fast path aborts, we can safely remove those assignments in
when the starting conditions for that fast path are satis ed. the middle of the fast path and improve performance.
This is su cient to ensure fairness in the generated code
even if the fast path code does not handle nondeterminism 5. IMPLEMENTATION
fairly.
To demonstrate the techniques described in this paper,
Our approach to handle fairness on the fast path is not
we have implemented the automatic fast path generation in
only simple but also presents an opportunity to avoid the
our ESP [21] compiler. ESP is a concurrent domain-speci c
overhead due to nondeterminism in the fast path. Recall
language designed to write rmware for programmable de-
that the nondeterminism ov
Contact this candidate