# Toward a Core Design to Distribute an Execution on a Many-Core Processor

Bernard Goossens, David Parello, Katarzyna Porada, Djallal Rahmoune

► To cite this version:

Bernard Goossens, David Parello, Katarzyna Porada, Djallal Rahmoune. Toward a Core Design to Distribute an Execution on a Many-Core Processor. PaCT: Parallel Computing Technologies, Aug 2015, Petrozavodsk, Russia. pp.390-404, 10.1007/978-3-319-21909-7_38. hal-01152664

HAL Id: hal-01152664

https://hal.science/hal-01152664

Submitted on 18 May 2015

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Toward a Core Design to Distribute an
Execution on a Many-Core Processor

Bernard Goossens, David Parello, Katarzyna Porada, and Djallal Rahmoune

DALI, UPVD 66860 Perpignan Cedex 9 France,
LIRMM, CNRS: UMR 5506 - UM2 34095 Montpellier Cedex 5 France,
{bernard.goossens,david.parello,katarzyna.porada,djallal.rahmoune}@univ-perp.fr

**Abstract.** This paper presents a parallel execution model and a many-core processor design to run C programs in parallel. The model automatically builds parallel sections of machine instructions from the run trace. It parallelizes instructions fetches, renamings, executions and retirements. Predictor based fetch is replaced by a fetch-decode-and-partly-execute stage able to compute in-order most of the control instructions. Tomasulo's register renaming is extended to memory with a technique to match consumer/producer pairs. The Reorder Buffer is adapted to allow parallel retirement. The model is presented on a *sum* reduction example which is also used to give a short analytical evaluation of the model performance potential.

**Keywords:** Microarchitecture, Parallelism, Manycore, Automatic parallelization

# 1 Introduction

Every parallel machine programmer dreams he can run his unchanged C programs on a parallel computer.

Figure 1 shows a C version and a *pthread* version of a *sum* reduction function.

The difference does not lie in the code text (based on the same algorithm) but in its execution. The C code is run sequentially using a stack and the *pthread* code is run in parallel with the help of the *pthread* system primitives.

This paper aims to show that if we change the execution model, the C code run can have the same behaviour as the *pthread* run, i.e. parallel execution. But of course, the C code is much simpler. Section 2 explains how to run a C program in parallel. Section 3 evaluates the Instruction Level Parallelism (ILP) in benchmarks based on parallel algorithms and lists the main published works on ILP. Section 4 describes the parallel execution model and its core microarchitecture. Section 5 gives an analytical evaluation of the performance potential of the proposed model and core design. It also mentions the on-going developments of simulators and concludes.
```c
unsigned long
sum(unsigned long t[]), unsigned long n){
    if (n==1) return t[0];
    else if (n==2) return t[0]+t[1];
    else return sum(t,n/2) + sum(&t[n/2],n-n/2);
}

(a) C implementation
```

```c
typedef struct {unsigned long *p; unsigned long i;} ST;
void =sum(void *st){
    ST str1, str2, unsigned long s,sl,s2;
    pthread_t tid1, tid2;
    if (((ST *)st)->i>2){
        str1.p=((ST *)st)->p; str1.i=((ST *)st)->i/2;
        pthread_create(&tid1,NULL, sum, (void*)&str1);
        str2.p=((ST *)st)->p + ((ST *)st)->i/2;
        str2.i=((ST *)st)->i - ((ST *)st)->i/2;
        pthread_create(&tid2,NULL, sum, (void*)&str2);
        pthread_join, (void*)&s1);
        pthread_join(tid2, (void*)&s2);
    }
    else if (((ST *)st)->i==1){s1=((ST *)st)->p[0];s2=(ST *)st)->p[1];}
    else {s1=((ST *)st)->p[0];s2=((ST *)st)->p[1];}
    s1=s1+s2; pthread_exit((void *)s);
}

(b) pthread implementation
```

<caption>Fig. 1: A vector sum reduction: C and pthread implementations</caption>

## 2 Running a C program in parallel.

Figure 2 shows the sum function translation into x86 (gas syntax; rightmost operand is the destination). The code is run sequentially because the hardware is unable to fork at lines 12 and 20. The control flow travels along the binary tree of calls depth first, leading to a 59 instructions run trace shown on figure 3 (figure 4 left part shows the call tree for sum(t,5)).

<figure><img src="image_2.png" /><figcaption>Fig. 2: The sum function in X86</figcaption></figure>

Figure 5 shows a modified x86 code for the sum function. The hardware is assumed to be able to fork, i.e. start a second instruction flow which occurs on lines 10 and 16 (fork instructions replace call instructions of the original x86 code). Unlike a call instruction, a fork instruction does not save a return address.

Non volatile registers (i.e. rbx, rdi and rsi in this example) are copied to the forked path, replacing the stack save/restore pair. Hence push and pop are removed. The stack pointer itself (rsp) is copied to the forked path<fnref n="1" />.

<footnote n="1">¹ the stack in each section keeps its local variables, e.g. temp on figure 5.</footnote>
<figure><img src="image_3.png" /><figcaption>Fig. 3: The instruction trace for the run of sum(t, 5).</figcaption></figure>

The endfork instruction ends a flow. Unlike a return, the endfork does not give control back to a return address.

<figure><img src="image_4.png" /><figcaption>Fig. 4: The call tree (left) for the run of sum(t, 5) and its sections (right).</figcaption></figure>

Figure 6 shows how the run is parallelized. The run starts on core 1 which fetches and executes instructions 1-1 to 1-5. The fork instruction starts a new flow on core 2. The new flow matches the resume path after fork, i.e instruction subq on line 11 (figure 5). Core 1 continues its own flow (callee path back to line 1, instruction cmpq ). Both flows are run in parallel, leading to the fetch and execution of instructions 1-6 to 1-11 (core 1 flow) and 2-1 to 2-16 (core 2 flow).

As core 2 receives valid copies of registers rdi, rsi, rbx and rsp , instructions 2-1 and 2-3 to 2-6 can be executed. Only instruction 2-2 must wait until register rax is set by core 1 flow. The synchronisation need is easy to detect, thanks to register renaming. Instruction 2-2 consumes a source rax produced by the
closest instruction writing to *rax* on the sequential path. As soon as instruction 1-10 writes to *rax*, the written value is forwarded to instruction 2-2.

<figure><img src="image_5.png" /><figcaption>Fig. 5: The *sum* function in X86 modified by *fork* instructions.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 6: The instruction trace for the parallel run of *sum(t,5)*.</figcaption></figure>

The full run is divided into 5 flows or *sections* (figure 4, right part). Each section is framed by a red rectangle. The longest section is composed of 16 instructions (section 2, from 2-1 to 2-16). Sections are numbered in execution trace order as indicated by the green arrows. Instructions framed by a blue rectangle belong to the same call level (e.g. instructions 1-1 to 1-5, 2-1 to 2-6
and 5-1 to 5-3 form the same call level). A section is a full recursive descent (e.g. section 1 combines 1-1 to 1-5 for *n* = 5 and 1-6 to 1-11 for *n* = 2).

Out-of-order execution is crucial to parallelize fetch. As instruction 2-2 does not block 2-6, the second call can be run in parallel with the first one.

This example shows that if the hardware is changed, the *sum* function can
run in parallel as in the *pthread* implementation. However, any link between
threads in the *pthread* or *MPI* models must be explicitely added to the code
through OS communication primitives (e.g. *MPI Send* and *MPI Recv* or socket
based communications in *pthread*).

In the parallel model, the sections are totally ordered. New sections are in-
serted in place in the list of existing sections, possibly in parallel, building the
sequential trace of the run. This structure and the renaming process (which as-
signs a new location to each write of each instruction in the sequential trace)
ensure that each read can match the most recent preceding write. In the *pthread*
or *MPI* models, this sequential structuration of threads is not available.

For example, if *x* is local to thread *t*<sub>*y*</sub> and *y* is local to thread *t*<sub>*y*</sub>, to copy *y* into *x* thread *t*<sub>*y*</sub> sends *y* to thread *t*<sub>*x*</sub>, which receives it (*MPI* rendezvous). If *x* is global, *t*<sub>*x*</sub> and *t*<sub>*y*</sub> can communicate through *x* but they must synchronize writes and reads with *pthread* mutex. The OS must be invoked to link the sender and the receiver or to synchronize multiple writers and readers.

In the parallel model, the equivalent of thread *t*<sub>*y*</sub> is section *s*<sub>*y*</sub> writing to *y* and the equivalent of thread *t*<sub>*x*</sub> is section *s*<sub>*x*</sub> reading *y* to copy it into *x*. Section *s*<sub>*y*</sub> has instruction *i*<sub>*y*</sub> writing to *y* (say *i*<sub>*y*</sub> is `addq %rbx`, `%rax`, with *y* in *rax*, i.e. *y* = *y* + *z* for some *z* in *rbx*) and section *s*<sub>*x*</sub> has instruction *i*<sub>*x*</sub> reading *y* (say *i*<sub>*x*</sub> is `movq %rax`, `%rcx`, with *rcx* being *x*, i.e. *x* = *y*). Instruction *i*<sub>*y*</sub> allocates *rax*<sub>0</sub> to rename *rax* destination. Instruction *i*<sub>*x*</sub> renames its source *rax*. As sections *s*<sub>*y*</sub> and *s*<sub>*x*</sub> are ordered and as no instruction updates *y* between *i*<sub>*y*</sub> and *i*<sub>*x*</sub>, the renaming of *rax* in *i*<sub>*x*</sub> matches *rax*<sub>0</sub>. Moreover, the hardware synchonizes the reader *i*<sub>*x*</sub> with the writer *i*<sub>*y*</sub> until *rax*<sub>0</sub> is full. Hence, rendezvous or mutex are not necessary and the OS need not be sollicited.

Renaming is the key to synchronization and communication between depen-
dent flows. Renaming should be extended to all hardware locations. For example,
instruction 5-1 reads the top of stack word (0(*rsp*)). This memory location is
written by instruction 2-2. If instruction 2-2 destination *a* = 0(*rsp*) is renamed
*r*, instruction 5-1 renames the same address *a* with the same name *r*, exhibiting
the dependency with instruction 2-2. Instruction 5-1, which computes the final
sum, executes after it has received *rax* from section 4 (second half of the sum)
and *a* from section 2 (first half of the sum).

3 ILP in programs

Figure 7 displays the ILP of ten benchmarks of the PBBS suite [1]. The PBBS
benchmarks implement various classical parallel algorithms (see table 1).

On figure 7, for each of the 10 benchmarks, the 11 leftmost bars (those with
numbered keys) match eleven parallel runs of the benchmark with increasing
<figure><img src="image_7.png" /><figcaption>Fig. 7: ILP of ten benchmarks parallel and sequential runs</figcaption></figure>

<table><caption>Table 1: Ten benchmarks of the PBBS suite</caption><thead><tr><th></th><th>Benchmark</th></tr></thead><tbody><tr><td>01</td><td>breadthFirstSearch/ndBFS</td></tr><tr><td>02</td><td>comparisonSort/quickSort</td></tr><tr><td>03</td><td>convexHull/quickHull</td></tr><tr><td>04</td><td>dictionary/deterministicHash</td></tr><tr><td>05</td><td>integerSort/blockRadixSort</td></tr><tr><td>06</td><td>maximalIndependentSet/ndMIS</td></tr><tr><td>07</td><td>maximalMatching/ndMatching</td></tr><tr><td>08</td><td>minSpanningTree/parallelKruskal</td></tr><tr><td>09</td><td>nearestNeighbors/octTree2Neighbors</td></tr><tr><td>10</td><td>removeDuplicates/deterministicHash</td></tr></tbody></table>

datasets. The rightmost bar (blue colour, seq11 key) matches sequential runs with the same dataset as key 11 parallel runs.

The sequential runs consider all the dependencies excluding the register false ones (Write After Read and Write After Write), assuming an unlimited register renaming capacity, and excluding the control flow ones, assuming perfect branch prediction. The sequential runs ILP measures the ultimate performance of actual out-of-order speculative processors.

The parallel runs assume the trace is available when the run starts (no fetch delay) and in the same time all the destinations (including memory) are renamed. The stack pointer dependencies are not considered. The parallel runs ILP measures the ultimate performance an ideal parallel machine achieves when the run order only depends on the producer to consumer dependencies, excluding the stack pointer. Each instruction on the trace is run at the cycle next to the last source reception. The processor is assumed to run all the ready instructions in the same cycle with a single cycle latency (as in the sequential runs).
All runs are continued until completion. For each benchmark, the 11 parallel
runs vary from 1M to 1G instructions (increasing factor 2) and the sequential
runs are 1G instructions long.

The figure shows that sequential runs have a very low ILP (ranging from 3.2 to 5.6) and parallel runs have a very high ILP (ranging from 600 to 508K for dataset 11). The difference comes from the dominating distant ILP. Moreover, when a benchmark is data parallel its parallel run ILP increases proportionally to the dataset (e.g. benchmarks 1, 2, 5, 6, 9 and 10).

The sequential run ILP we have measured confirms ILP reported values (such as [6]). Since 50 years many successive research works on ILP were published.

In 1967, Tomasulo [3] presented an algorithm to run floating point instructions out-of-order. He introduced register renaming which is still used in today's speculative cores to parallelize on-the-fly instructions. In 1970, Tjaden and Flynn [4] measured the available parallelism in a 10 instructions window. They ran their test programs at 1.86 instructions per cycle.

In 1984, Nicolau and Fisher [5] measured the available parallelism to feed a VLIW processor. In their experiments, they included a measure of ILP from runs on an ideal machine with infinite resources. They discovered that scientific codes present a high ILP, over 1000.

In 1991, David Wall presented the first study centered on ILP[6]. He measured that the available parallelism a “real” processor finds in 13 benchmarks is 5 on average, ranging from 3 to 45². In an “ideal” processor<fnref n="3" />, ILP ranges from 6 to 60 with an average at 25. From this study, we know that there is ILP but it seems impossible to catch more than 5 independent instructions per cycle.

In 1992, Austin and Sohi [7] measured the SPEC89 suite ILP and analyzed its distribution. They showed that ILP is arbitrarily distant from the instruction pointer. They also pointed out the serializing effect of the stack manipulations. The same year, Lam and Wilson [8] studied the impact of control on ILP. Their measures showed that a processor with a perfect branch predictor could dramatically improve its performance. As in Austin and Sohi work, distant ILP was detected. To capture this distant ILP, a processor must be able to speculate on the control flow and use multiple instruction pointers. In 1997, Moshovos and Sohi have proposed memory renaming in [9], using a predictor to find the store renaming a load. In 1999, Postiff, Greene, Tyson and Mudge [10] measured SPEC95 suite ILP. They pointed out that the stack introduces many parasitic dependencies. To capture distant ILP, the application should be multi-threaded.

In 2004, Cristal, Santana and Valero [11] described a kilo-instructions microarchitecture. The authors suggested that to capture more ILP, the processor must have access to instructions far from the fetch point. They gave solutions to allocate later and free sooner the needed resources to optimize their usage and so, take care of more "on-the-fly" instructions with the same resources. In

<footnote n="2">² “good” model with a 2K instructions window size, 64 instructions issued per cycle, 256 renaming registers, a branch predictor based on an infinite number of 2-bits counters and a perfect memory aliasing disambiguation</footnote>

<footnote n="3">³ “perfect” model enhances “good” model: infinite renaming, perfect branch predictor.</footnote>
2012, Sharafeddine, Jothi and Akkary [12] proposed an architecture to partition a run into parallel threads, forking the leading thread at call. In the sum example this leads to fork on both of the highest levels calls but not on the lower levels, capturing only a small part of the distant ILP. In 2013, Goossens and Parello [13] analyzed distant ILP and showed that ILP could be highly increased when removing stack pointer updates and false memory dependencies.

From these works, we deduce that i) high ILP is available, ii) most of it comes from very distant instructions and iii) sequential fetch and stack are the main obstacles on the ILP capture. Two ideas are suggested to help capture distant ILP : following multiple instruction flows [8] and renaming memory [9].

# 4 An execution model to run programs in parallel and its core implementation.

In section 3 we assumed the full trace is available at run start and all the destinations are pre-renamed. This is not realistic. However, code fetch and destinations renamings should occur as soon as possible to allow distant ILP capture.

## 4.1 Parallelizing fetch.

A section is composed of dynamically contiguous instructions. A section starts when a *fork* instruction creates it. It ends when an *endfork* instruction is reached. A control flow instruction (jump, call or branch) does not end a section. The same section continues after the control flow instruction.

When a new section is forked, a message is sent to a hosting core<fnref n="4" />. The message contains the forked Instruction Pointer (IP), the stack pointer and the set of non volatile registers. It also contains the identification of the neighbour sections (e.g. the current creating section). The choosen core queues the message while it fetches another section. When the section creation message is dequeued, it fills the register file local to the fetch pipeline stage. The IP, the stack pointer and the non volatile registers are initialized and other registers are emptied.

For example, when instruction 1-5 forks, a section creation message is sent to core 2 (say), including register *rdi* value *t*, register *rsi* value 2 and register *rbx* value 5. When instruction 2-6 forks, the stack pointer *rsp* is transmitted to section 5, pointing on the same stack word as section 2. Hence, sections 2 and 5 share the same stack portion. Thanks to memory renaming, when instruction 5-1 reads stack word 0, it matches with instruction 2-2 write to stack word 0. Both instructions compute the same address $a = rsp + 0$.

The fetch pipeline stage fetches along the section pointed to by IP. The fetch stage has no branch predictor. There are two reasons for such a choice. First, moving fast along the flow is better obtained by a parallel fetch along multiple control-computed sections than by a sequential fetch along a single predicted path, even if the prediction is perfect. Second, a predictor is less cost-effective

<footnote n="4">⁴ hosting core choice to optimize load balancing is out of the scope of this paper.</footnote>
in a core if the flow is divided into sections and distributed on multiple cores. For these reasons, the fetch stage computes its control rather than predicting it. To keep the stage hardware simple, each cycle fetches and computes a single instruction. As a result, each core fetches more slowly than an actual speculative core but the cores fetch much faster altogether.

Figure 8 shows the fetch-and-decode pipeline stage. The IP addresses the Instruction Memory Hierarchy (IMH, i.e. L1 instruction cache). The fetched instruction addresses the Register File (RF) to read full registers sources. If all the needed sources are full, the instruction is computed in the ALU. Floating point instructions, memory accesses, complex integer instructions and instructions having empty sources are not computed in the fetch stage but later. Computed instructions results are written back to RF, setting the destination register to full. Uncomputed instructions set their destination register(s) to empty.

The fetch stage includes instruction decoding (not shown). When a *fork* instruction is decoded, it generates a section creation message. The created section starts at the next instruction. The current section continues at the *fork* instruction target. It ends when an *endfork* instruction is decoded. The IP register is set to empty and at the next cycle the *PIO* head message is DeQueued and IP and RF are initialized, which starts the fetch of a new section.

As mentioned on figure 8, the stage critical path is longer than in a speculative out-of-order pipeline, including a L1 cache traversal, an instruction decoding, a register file read (2 read ports), an ALU (Arithmetic and Logic Unit) computation and a register file write (1 write port). This leads to a slow frequency processor, such as a GPU. Slowness is to be compensated by parallelism.

<figure><img src="image_8.png" /><figcaption>Fig. 8: Fetch-decode pipeline stage</figcaption></figure>

## 4.2 Core pipeline microarchitecture.

Figure 9 shows the six-stages pipeline building the core microarchitecture. On the bottom part of the design we find a full size rectangle dedicated to commu-
Instructions retire in-order (within their section) by exporting their result to the successor section<fnref n="6" />. To be retired, an instruction must be terminated. An instruction is not exported if it holds a result useless for successors, i.e. if i) its destination is updated later in the section or ii) it writes to a non volatile register or iii) it is a control flow instruction or iv) it writes to stack or heap in a location freed later in the section or v) it has exported its computation to a consumer. The successor discards exported instructions if their production may not be consumed anymore. An exported instruction *i* is discarded by the successor section *s*′ if *i* writes to a destination renamed or freed in *s*′.

An exported instruction is accepted by the successor section *s'* only if its
destination is neither the source nor the destination of any instruction in *s*'.

In the *sum* function example, no instruction is exported. For example, the
instruction consuming the final sum to be displayed receives its source from
instruction 5-1 which does not need to be exported (statement v).

An exported instruction is sent to the successor section through the IERU. It
is received in the RRRU (register write) or in the ARRU (memory write). The
destination is tentatively renamed and in case of a hit the exported instruction
is discarded (already renamed destination). It is also discarded if it writes to
stack or heap in a location later freed by the section. Otherwise, the instruction
gets a new local renaming and is saved in its new section ROB.

**What is new in the proposed core design?** The core shown on figure 9 is much simpler than actual speculative cores. The core is as small as possible to maximize the number of cores on the die. As the core is not speculative, there is no predictor nor renaming repair unit (checkpoints). The LSQ is simpler than the usual Load-Store Queue as loads are not speculative and store-to-load forwarding is not necessary. The data memory hierarchy is kept coherent as only the oldest section can write to and read from it. There is no memory coherency hardware (e.g. MESI protocol handler). There is no vector computing unit (e.g. XMM-like) as vectorization is better obtained through parallelism. Each core implements a single instruction path (no superscalar or VLIW path).

5 Analytical performance evaluation of the parallel execution model on the *sum* example and conclusion.

Figure 10 shows 5 tables (one per core) giving the execution timing of the *sum(t,5)* run. The instructions numbers are given on the left of each table. The columns of a table match the 6 pipeline stages. A value in a column represents the cycle at which the instruction is treated by the corresponding pipeline stage. For example, instruction 1-8 (load) is handled by core 1, fetched at cycle 8, register renamed at cycle 9, load address is computed at cycle 10 and renamed at

<footnote n="6">⁶ The oldest section, i.e. the only one with no predecessor, dumps its renamings to the data memory hierarchy (DMH). When it receives a renaming request which misses, it loads from DMH and exports the loaded line.</footnote>
<figure><img src="image_9.png" /><figcaption>Fig. 10: Execution timing of the sum(t,5) run.</figcaption></figure>

cycle 11, renamed memory is accessed at cycle 14 (counting 3 cycles to reach the producer and return the t[0] value) and retired at cycle 15. We assume the 5 sections can be hosted in 5 different cores. We also assume each pipeline stage manipulates a single instruction. Instruction cache L1 is assumed to always hit. From this example we see that the code is fetched in 30 cycles (last fetched instruction is 3-12), i.e. 1.5 instructions per cycle. If the data size is doubled, the fetch time is 42 cycles (104 instructions fetched, i.e. 2.5 instructions per cycle). Only fetch latency (i.e. IL1 miss rate) can impact the fetch time. It is independent of renaming and execute latencies.

The number of instructions is $45 * 2^n + 14 * (2^n - 1)$ for the sum of a $5 * 2^n$ elements array (i.e. 45 for sum(t,5), 104 for sum(t,10)). The fetch time is $30 + 12 * n$ (i.e. 30 for sum(t,5), 42 for sum(t,10)). For 1280 elements, 15090 instructions are fetched in 126 cycles, i.e. 120 instructions per cycle. This shows that even though one instruction is fetched per cycle per core and the control is computed rather than predicted, fetching in parallel is efficient. Even for modest data sizes, it outperforms any speculative fetching hardware.

Renaming is not penalized by the distribution of the code nor by its extension to memory locations. Most of the sources are provided by register value copy at fork. Function results and stack local variables are obtained from the predecessor section. Global variables are reached quickly from the first section (which starts at the main function entrance) and then fastly propagated to other sections, thanks to full memory line caching. Eventually, instruction retirement frees the resources at the same rate they are allocated, avoiding cores saturations. The retirement time is$^7 43 + 15 * n$. For 1280 elements, the 15090 instructions are retired in 163 cycles, i.e. 92 instructions per cycle.

<footnote>$^7$ 15 cycles is the fetch time of instructions (figure 5) 2, 3, 8-10 (5 cycles), the creation time of the forked section (2 cycles), the fetch time of instructions 11-16 (5 cycles) and the retirement of instructions 17-19 (3 cycles).</footnote>
Devil is in the details. Fine simulation of the model is necessary to prove that distant ILP present is captured. Two such simulators are on-going projects: a VHDL implementation of the core pipeline and a *qemu* and *simplescalar* based simulator to quantify the IPC performance of a many-core processor.

The model presented focuses on functions. In the same way, loops can be par-
allelized. *For* loops can be vectorized, each iteration forming a separate section
with no control. It heritates its iteration counter that can be saved in a register
and used in the iteration body. *While* loops can be parallelized, launching each
iteration in sequence (no speculation) but parallelizing their bodies.

With the introduction of many-core chips as general purpose processors, the
time has come to produce parallel programs automatically. This paper suggests
that we are not so far from the goal and the hardware can greatly help.

References

1. Shun, J., Blelloch, G.E., Fineman, J.T., Gibbons, P.B., Kyrola, A., Simhadri, H.V., Tangwongsan, K.: Brief announcement: The problem based benchmark suite. In: Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures. SPAA '12 (2012) 68–70

2. Wall, D.W.: Limits of instruction-level parallelism. In: Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. ASPLOS IV (1991) 176–188

3. Tomasulo, R.M.: An efficient algorithm for exploiting multiple arithmetic units. IBM J. Res. Dev. 11(1) (January 1967) 25–33

4. Tjaden, G.S., Flynn, M.J.: Detection and parallel execution of independent instructions. IEEE Trans. Comput. 19(10) (October 1970) 889–895

5. Nicolau, A., Fisher, J.: Measuring the parallelism available for very long instruction word architectures. Computers, IEEE Transactions on C-33(11) (1984) 968-976

6. Wall, D.W.: Limits of instruction-level parallelism. In: WRL Technical Note TN-15. (1990)

7. Austin, T.M., Sohi, G.S.: Dynamic dependency analysis of ordinary programs. In: Proceedings of the 19th annual international symposium on Computer architecture. ISCA '92 (1992) 342–351

8. Lam, M.S., Wilson, R.P.: Limits of control flow on parallelism. In: Proceedings of the 19th Annual International Symposium on Computer Architecture. ISCA '92 (1992) 46–57

9. Moshovos, A., Breach, S.E., Vijaykumar, T.N., Sohi, G.S.: Dynamic speculation and synchronization of data dependences. In: Proceedings of the 24th Annual International Symposium on Computer Architecture. ISCA '97 (1997) 181–193

10. Postiff, M.A., Greene, D.A., Tyson, G.S., Mudge, T.N.: The limits of instruction level parallelism in spec95 applications. CAN **27**(1) (1999) 31–34

11. Cristal, A., Santana, O.J., Valero, M., Martínez, J.F.: Toward kilo-instruction processors. ACM Trans. Archit. Code Optim. **1**(4) (December 2004) 389–417

12. Sharafeddine, M., Jothi, K., Akkary, H.: Disjoint out-of-order execution processor. Transactions on Architecture and Code Optimization (TACO) **9**(3) (sept 2012) 19:1–19:32

13. Goossens, B., Parello, D.: Limits of instruction-level parallelism capture. Procedia Computer Science **18**(0) (2013) 1664–1673 2013 International Conference on Computational Science.