Compiler Control Power Saving Scheme forMulti Core Processors
Jun shirako† , Naoto Oshiyama† , Yasutaka Wada† , Hiroaki Shikano‡ ,Keiji Kimura†‡ , and Hironori Kasahara†‡†

Dept. of Computer Science, ‡ Advanced Chip Multiprocessor Research Institute
Waseda University
3-4-1 Ohkubo, Shinjuku-ku, Tokyo, 169-8555, Japan{shirako,oshiyama,yasutaka,shikano,kimura,kasahara}@oscar.elec.waseda.ac.jp

Abstract. With the increase of transistors integrated onto a chip, multicore processor architectures have attracted much attention to achieve
high effective performance, shorten development period and reduce thepower consumption. To this end, the compiler for a multi core processor
is expected not only to parallelize program effectively, but also to control
the voltage and clock frequency of processors and storages carefully inside an application program. This paper proposes a compilation scheme
for reduction of power consumption under the multigrain parallel processing environment that controls Voltage/Frequency and power supplyof each processor core on a chip. In the evaluation, the OSCAR compiler with the proposed scheme achieves 60.7 percent energy savings forSPEC CFP95 applu without performance degradation on 4 processors,and 45.4 percent energy savings for SPEC CFP95 tomcatv with real-time
deadline constraint on 4 processors, and 46.5 percent energy savings forSPEC CFP95 swim with the deadline constraint on 4 processors.

1

Introduction

According to the increase of transistors integrated onto a chip, a chip multiprocessor architecture, or multicore architecture, that can achieve higher performance and save the power consumption is collecting much attention as future
processors. To realize efficient parallel processing on multiprocessor systems,
cache and local memory optimization to cope with memory wall problems andminimization of data transfer among processors using DMAC (Direct Memory
Access Controller), in addition to the extraction of parallelism from an application program. For the exploitation of parallelism for multiprocessors, there
have been a large number of researches in the areas of loop parallelizing compilers [1–3]. However, the loop parallelization techniques are almost matured
and new generation of parallelization techniques like multi-grain parallelization
are required to attain further speedup. There are a few compilers trying to exploit multiple levels of parallelism, for example, NANOS compiler[4] extracts
the multi-level parallelism including the coarse grain task parallelism by using
extended OpenMP API and OSCAR multigrain parallelizing compiler [5–7] extracts coarse grain task parallelism among loops, subroutines and basic blocks

and near fine grain parallelism among statements inside a basic block, in addition to the loop parallelism. Also, OSCAR compiler realizes the automatic
determination of parallelism of each part of a program and the number of required processors to process the program part efficiently with the global cachememory optimization over different loops.
This required number of processors determination scheme determines thesuitable number of processors to execute each part of a program and stops theunnecessary processors to minimize processing overhead and reduce power consumption by shutting off power supply for idle processors.
For the power saving techniques, various methods have been proposed. Adaptive Processing[8] estimates the workload of computing resources using counters
for cache misses and instruction queues and powers off unnecessary resources.
Online Methods for Voltage and Frequency Control [9] settles on the fitting voltage and frequency for each domain of processors using instruction issue queue occupancies as feedback signals. As the compiler algorithm for CPU energy reduction, compiler-directed DVS(dynamic voltage scaling)[10] is known. This method
gets the relations between frequency and execution time for each part of a program by profiling. It solves minimization problem of total energy consumption
and determines the suitable frequency for each part.
This paper proposes a static compiler control scheme of power saving for a
multi core processor without profiling, which realizes– power supply cutoff for unnecessary processors– voltage/frequency(V/F) control of each task or of each processor in an application program under the constraints of the minimum time execution or
the satisfaction of real-time deadline

2

Multigrain parallel processing

The proposed power saving scheme is mainly used with the coarse grain task
parallelization in the multigrain parallel processing. This section describes theoverview of the coarse grain task parallel processing.

2.1

Generating macro-tasks [5–7][11, 12]

In multigrain parallelization, a program is decomposed into three kinds of coarse
grain tasks, or macro-tasks, such as block of pseudo assignment statements(BPA)
repetition block(RB), subroutine block(SB)[7]. Macro-tasks can be hierarchicallydefined inside each un-parallelizable repetition block, or sequential loop, and asubroutine block as shown in Figure 1. Repeating the macro-task generation
hierarchically, the source program is decomposed into the nested macro-tasks as
in Figure 1.

BPA

Near fine grain parallelism
Loop level parallelism

Program

RB

BPA
RB
SB

Near fine grain parallelism
in loop body
Coarse grain parallelism

SB
all system 1st layer

Coarse grain parallelism

BPA
RB
SB

2nd layer

BPA
RB
SB
BPA
RB
SB
BPA
RB
SB
BPA
RB
SB
3rd layer

Fig. 1. Hierarchical Macro Task Definition

2.2

Extraction of coarse grain task parallelism

After generation of macro-tasks, the data dependency and the control flow among
macro-tasks are analyzed in each nested layer, and hierarchical macro flow
graphs(MFG) representing control flow and data dependencies among macrotasks are generated [5–7]. Then, to extract coarse grain task parallelism among
macro-tasks, Earliest Executable Condition analysis [5–7] which analyzes control dependencies and data dependencies among macro-tasks simultaneously isapplied to each Macro flow graph. Earliest Executable Conditions are the conditions on which macro-task may begin its execution earliest. By this analysis,a macro-task graph(MTG)[5–7] is generated for each macro flow graph. Macrotask graph represents coarse grain parallelism among macro-tasks.
2.3

Processor groups and Processor elements

To execute hierarchical macro-task graphs efficiently, the compiler groups processors hierarchically. This grouping of processor elements(PEs) into Processor
Groups(PGs) is performed logically, and macro-tasks are assigned to processor
groups in each layer.
Figure 2 shows an example of a hierarchical processor groups. For executionof a macro-task graph in the 1st nest level, or 1st layer, the 8 processors aregrouped into 2 processor groups each of which has 4 processor elements. Thisis represented as (2PGs, 4PEs). The macro-task graph in the 1st nest levelis processed by the 2PGs. For each macro-task graph in the 2nd nest level, 4
processors are available. In the Figure 2, the grouping of (4PGs, 1PE) is chosen
for the left PG and (2PGs, 2PEs) is chosen for the right PG.
2.4

Automatic determination scheme of parallelizing layer

In order to improve the performance of multigrain parallel processing, it is necessary to schedule the tasks on the macro-task graph with the extracted parallelism

0th layer
1st layer
2nd layer

8PE
PG0(4PE)
PG1-0(2PE)

PG1-1(2PE)

PG1(4PE)
PG0-0

PG0-1

PG0-2

PG0-3

Fig. 2. Hierarchical definition of processor groups and processor elements

to processors the grouped processor layer. OSCAR compiler with the automaticparallelized layer determination scheme [11, 13] estimates the parallelism of eachmacro-task graph and determine the suitable (PGs, PEs) grouping. This scheme
determines the suitable number of processors executing each macro-task, considering trade-off between parallelization and scheduling and data transfer overhead. Therefore, OSCAR compiler doesn’t assign tasks to the excessive processors to reduce parallel processing overhead.
2.5

Macro-Task SchedulingIn the coarse grain task parallel processing, a macro-task in the macro-task
graph is assigned to a processor group. At this time, static scheduling or dynamicscheduling is chosen for each macro-task graph.
If a macro-task graph has only data dependencies and is deterministic, thestatic scheduling is selected. In this case, the compiler schedules macro-tasks toprocesser groups. The static scheduling is effective since it can minimize datatransfer and synchronization overhead without runtime scheduling overhead.
If a macro-task graph is un-deterministic by conditional branches amongcoarse grain tasks, the dynamic scheduling is selected to handle the runtime
uncertainties. The dynamic scheduling routines are generated by the compiler
and inserted into a parallelized program code to minimize scheduling overhead.
This paper proposes the power saving static scheduling scheme for the determinable macro-task graphs.
In the following sections, MT represents macro-task, MTG is macro-task
graph, PG is processor group, PE is processor element, BPA is block of pseudo
assignment statements, RB is repetition block and SB is subroutine block.

3

Compiler control power saving scheme

The multigrain parallel processing can take full advantage of multi level parallelism in a program. However, there isn’t always enough parallelism in all part ofa program for available resources. In such a case, shutting off the power supply
to the idle processors, to which tasks are not assigned, can reduce power consumption. Also, execution at lower voltage and frequency may reduce the totalenergy consumption in real time processing with the deadline constraint. The
proposed scheme realizes the following two modes of power reduction. The firstTable 1. The rate of frequency, voltage, dynamic energy and static power

state
FULL MID LOW OFF
frequency1
1/2 1/4
0
voltage10.87 0.71 0
dynamic energy 1
3/4 1/2
0
static power
1
1
1
0

is the fastest execution mode that doesn’t apply the power saving scheme to thecritical path of a program to guarantee the fastest processing speed. The second
is real-time processing mode with deadline constraint that minimizes the totalenergy consumption within the given deadline.
3.1

Target model for the proposed power saving scheme

In this paper, it is supposed that the target multi core processors have the following functions with the hardware supports like OSCAR multi core processor
shown in Figure 3. The OSCAR(Optimally Scheduled Advanced Multiprocessor)
architecture has been proposed to support optimization of multigrain parallelizing compiler [14, 5, 6], especially static and dynamic task scheduling [15, 14, 16].
In the OSCAR architecture, simple processor cores having local and/or distributed shared memory both of which are double mapped to the global address
space so that can be accessed by remote processor cores DTC(Data Transfer
Controller), or DMAC, are connected by interconnection network like multiple
busses or cross bar switches to control shared memory(CSM) [15, 14, 16, 17]. In
addition to the traditional OSCAR architecture, in this paper, the following
power control functions are supported.
– The frequency for each processor can be changed in several levels individually.
– The voltage can be changed with the frequency.
– Each processor can be powered on and off individually.
There are a lot of approaches for voltage and frequency(V/F) control. The proposed power saving scheme assumes frequency changes discretely, and the optimal voltage is fixed for each frequency. Table 1 shows an example of the combinations of voltage, dynamic energy and static power at each frequency, which
supposes FULL is 400MHz, MID is 200MHz and LOW is 100MHz at 90nm
technology. For the table, dynamic energy rate for each frequency is the rate ofenergy consumption to the energy consumption at FULL. The power supply isshut off completely at OFF, then the static power becomes 0. These parameters
and the number of frequency states can be changed, according to architectures
and technology. This scheme also considers the state transition overhead that isgiven for each state.

OSCAR Chip Multiprocessor for Multigrain Parallel Processing
SCM 0
SCM m

PE0

CPU
Adjustable
Pre-fetch
I-CacheLDM/
D-cache

PE1

I/O
I/O
Devices
Devices
CSM j

PE n

I/O
SCM k

DTC

DSM

Network Interface

CSM

Intra-chip connection network (Multiple Buses, Crossbar, etc )CSM / L2 Cache
Inter-chip connection network (Crossbar, Buses, Multistage network, etc)

Fig. 3. OSCAR architecture(Chip multiprocessor)

3.2

Target MTG for the proposed control scheme

OSCAR compiler selects dynamic scheduling or static scheduling for each MTG,
as to whether there is runtime uncertainty like conditional branches in the
MTG. The proposed scheme can be only applied to static scheduled MTGs.
However, separating the parts without branches from dynamic scheduled MTG,
this scheme is applied for the static scheduling parts of MTGs. In the static
scheduling at the compile time, execution cost and consumed energy of each
MT is estimated. The cost and energy at each frequency level like “FULL” and“MID” can be calculated using the previously prepared parameter table for eachtarget multicore processor of each instruction cost embedded in the compiler.
3.3

Deadline constraint of target MTG

The proposed scheme determines suitable voltage and frequency for each MT
on a MTG based on the result of static task assignment. In other words, theproposed power saving scheme is applied for the static task schedule like Figure
4 generated by static task scheduling algorithms to minimize processing time including data transfer overhead, such as CP/DT/MISF, DT/CP, ETF/CP, whichhave been used for a long time in OSCAR compiler. Figure 4 shows MTs 1, 2
and 5 are assigned to PG0, MTs 3 and 6 are assigned to PG1, MTs 4, 7 and 8
are assigned to PG2 by the static scheduling algorithms. The best schedule ischosen among different schedules generated by the different heuristic schedulingalgorithms. In Figure 4, edges among tasks show data dependence.
First, the following is defined for M Ti , in order to estimate the execution
time of the target MTG to which the proposed scheme is applied.
Ti : execution time of M Ti after V/F control
Tstarti : start time of M Ti

PG0

PG1

PG2
Phase 1

MT1
MT2

MT3

MT5

MT6

MT4

Phase 2MT7
MT8

Phase 3

Margintime

Given Dead Line

Fig. 4. static scheduled MTG

Tf inishi : finish time of M Ti
At the beginning of the proposed scheme, Ti is not yet fixed. The start time of
the target MTG is set to 0. If M Ti is the first macro-task executed by a PG
and has no data dependent predecessor. Tstarti and Tf inishi are represented asshown below.
Tstarti = 0
Tf inishi = Tstarti + Ti = Ti
For instance, the M T1 is the entry node of MTG, so it is the first and has nodata dependent predecessor. Then, Tstart1 = 0, Tf inish1 = T1 . In other case, theprevious macro-task which is assigned to the same PG as M Ti is represented as
M Tj . The data dependent predecessors of M Ti are defined as {M Tk , M Tl , ...}.
Then, M Ti starts when M Tj , M Tk , M Tl , ... finish.
Tstarti = max(Tf inishj , Tf inishk , Tf inishl , ...)
Tf inishi = Tstarti + Ti
In Figure 4, M T2 and M T3 start execution immediately after the time M T1 isfinished. So, the start time is represented as Tstart2 = Tstart3 = Tf inish1 = T1 , thefinish time is Tf inish2 = Tstart2 + T2 = T1 + T2 , Tf inish3 = Tstart3 + T3 = T1 + T3 .
M T6 is started after M T2 and M T3 , then Tstart6 = max(Tf inish2 , Tf inish3 ) =max(T2 + T1 , T3 + T1 ). In addition, the common term of the arguments in max
may be put out of max. Then, Tstart6 = max(T2 +T1 , T3 +T1 ) = max(T2 , T3 )+T1 .
As the same way, the finish time of M T8 which is the exit node is represented
as Tf inish8 = T1 + T8 + max(T2 + T5 , T6 + max(T2 , T3 ), T7 + max(T3 , T4 ))The exit node is generally represented by
Tf inishexit = Tm + Tn + ... + max1 (...) + max2 (...) + ...
The start time of the entry node is 0, therefore Tf inishexit expresses the execution
time of the target MTG, defined as TMT G . The given deadline for the target
MTG is defined as TMT G deadline . Then, the next condition should be satisfied.
TMT G ≤ TMT G deadline
The proposed scheme determines suitable clock frequency for M Ti to satisfy thecondition.

PG0

PG1

PG2

MT1

idle (1)idle (1)

MT2

MT3
MID

MT4

MT6

MT7

idle (2)

MT8

MT5
MID
idle (2)PG3idle (3)timeFig. 5. Result of FV control

3.4

Voltage / frequency control

This paragraph describes how to determine the voltage and frequency to execute each MT using next conditions. The execution time of M Ti is Ti , theexecution time of target MTG is TMT G , the real-time deadline of the terget
MTG is TMT G deadline , then
TMT G = Tm + Tn + ... + max1 + max2 + ... - - - (a)TMT G ≤ TMT G deadline - - - (b)For sake of simplicity, the MTs corresponding to each term of the expression (a)such as Tm , Tn , ..., max1 , max2 , ... are called Phase. Each term represents thedifferent part of TMT G . Therefore, the different Phase is not executed in parallelon any account as shown in Figure 4. The following parameters for P hasei atfrequency Fn are defined.
Tschedi (Fn ) : scheduling length at Fn
Energyi (Fn ) : energy consumption at Fn
Tschedi (Fn ) represents the execution time when the whole P hasei is processedat Fn . Tschedi (F U LL) is the minimum value of the term in the expression (a).
Energyi (Fn ) expresses the total energy consumption as P hasei is excuted atFn .
Here, it is considered to change frequency from Fn to Fm . The schedulinglength is increased from Tschedi (Fn ) to Tschedi (Fm ). The energy is decreased
from Energyi (Fn ) to Energyi (Fm ). Using these values, Gaini (Fm ) is defined asi (Fm )−Energyi (Fn )Gaini (Fm ) = − Energy
Tschedi (Fm )−Tschedi (Fn )Gaini (Fm ) represents reduction rate of energy on scheduling length when Fn ischanged into Fm . Therefore, if the increases of scheduling length are same, themore energy consumption can be prevented by prioritizing P hasei with larger
Gaini (Fm ).
Next, to estimate the margin of the target MTG, the minimum value of TMT G
is calculated. This is equal to the summation of Tschedi (F U LL). Then, using thisminimum value and TMT G deadline , theP margin TMT G margin is defined as
TMT G margin = TMT G deadline − Tschedi (F U LL)
As the target MTG must finish in minimum execution time, TMT G margin = 0,

Table 2. Power and frequency transition overhead

dynamic power
220[mW]static power
2.2[mW]
overhead(FULL - MID - LOW)
0.1[ms]overhead({FULL, MID, LOW} - OFF) 0.2[ms]then each Phase has to be executed at FULL. When TMT G margin > 0, theproposed scheme turns down the voltage and frequency of each Phase, according
to Gaini (Fm ). If Phase has a single MT, the frequency of MT is the same as thePhase. If Phase includes some MTs and corresponds to max term, the proposed
scheme also defines Phases for each argument of max, then determines clock
frequency to execute these Phases. The algorithm to determine frequency foreach Phase is described below. The initial value of each frequency is FULL.

Step.1 Determining each frequency of Phase
Step.1.1 selecting target Phase
This step considers only a Phase whose frequency isn’t fixed. Fn is represented
as current frequency and Fm is defined as one step lower than Fn , then P hasei
having the maximum Gaini (Fm ) is selected as the target Phase. goto Step.1.2
Step.1.2 determining effectiveness for target Phase
For target Phase, the conditions to change the frequency from Fn to Fm is asfollows.
1. Including the frequency transition overhead, the target Phase can finish at
Fm within the TMT G margin .
2. The energy at Fm with overhead is lower than the energy at Fn .
If both conditions are satisfied,then the frequency of target Phase is changed to Fm . goto Step.1.3
else the frequency of target Phase is confirmed as Fn . goto Step.1.4
Step.1.3 updating the margin of MTG
The required time to execute the target Phase at Fm is calculated, then therequired time is subtracted from TMT G margin . If Fm is the lowest frequency,
the frequency of target Phase is confirmed as Fm . goto Step.1.4
Step.1.4 determining exit
The conditions to exit are as follows.
1. The frequency of all Phase is confirmed.
2. TMT G margin is 0.
If either of these conditions is satisfied,then goto Step.2
else goto Step.1.1
The remained margin is given P hasei which satisfies next conditions, if TMT G margin
is not 0 at the end.

0

200M

PE0

PE1

DOALL6

DOALL7

PE3DOALL8

LOOP10MID

MID

DOALL14

LOOP11

OFF

DOALL15

LOOP12

OFF

DOALL16

LOOP13LOW

DOALL17

LOW
LOW

400M

PE2

OFF

OFF

OFF

DOALL9LOW

LOOP18

LOOP19
LOOP20600M

LOOP21

OFF
OFF

OFF

clock

Fig. 6. FV control of applu(4proc.)– The frequency is not the lowest.
– Gaini (Fm ) is the maximum.

Step.2 Voltage/frequency control within each Phase
In the proposed scheme, the following algorithm is applied to each Phase.
Step.2.1 classifying Phases
If Phase includes only a single MT,
then the frequency of the MT is the same as Phase. exit
else goto Step.2.2
Step.2.2 Voltage/frequency control of max termPhase includes some MTs and corresponds to max term, the proposed scheme
calculates the executing time of this Phase at the already determined frequency
in Step.1. Then, the calculated execution time is defined as Tmaxi deadline .
maxi = max(argi 1 , argi 2 , ...) ≤ Tmaxi deadline
argi j = Ti j m + Ti j n + ... + maxi j 1 + maxi j 2 + ...
Therefore, argi j should meet the next condition.
Ti j m + Ti j n ... + maxi j 1 + maxi j 2 ... ≤ Tmaxi deadline - - - (c)The MTs corresponding to each term in the expression (c) are also considered
as Phase, then Step.1 is applied to determine the frequency of each Phase. At
this time, the execution time of each argi j at FULL frequency is calculated.
Then each argi j is applied Step.1 in descending order of the execution time,or ascending order of the margin. Some Phases in different args may include thesame macro-tasks in common. However, once the frequency of a macro-task has
been determined, the frequency isn’t changed.
Applying Step.1 and Step.2 recursively, the suitable frequency of all MTs
are determined.

speedup ratio

4.5
4
3.5
3
2.5
2
1.5
1
0.5
0

w/o Saving
w Saving

1

2
4
tomcatv

1

2
4
swim
benchmark

1

2
applu

4

Fig. 7. Speedup in fastest execution mode

3.5

Power supply control

This paragraph explains power supply control to reduce unnecessary energy
consumption including static leak current by idle processors. The cases where
the idle time occurs in a MTG are,
1. before MT with data dependency is executed,
2. after all MTs in a PG are finished,
3. the idle time created by the determination scheme of parallelizing layer,
which is described in paragraph 2.4.
The gray parts of Figure 5 are the idle in each case. Here, the PG3 is theprocessor group determined as unnecessary. In the idle time which meets thenext conditions, the power of the processor is turned off.
– The idle time is longer than the frequency transition overhead.
– The energy becomes lower by power-off.

3.6

Applying power saving scheme to inner MTG

If a M Ti includes a M T Gi inside, it may be more effective to control each M Ti j
in M T Gi than to process the whole M Ti at the same clock frequency. Therefore,
the deadline for M T Gi is defined as TMT Gi deadline , which is given by Ti . Then,M T Gi is applied the proposed power saving control described in paragraph 3.4
and 3.5. Comparing both case to execute the whole M Ti at the same frequency
and case to apply the power saving control to M T Gi , the more effective one isselected.

energy(J)

200
180
160
140
120
100
80
60
40
20
0

w/o Saving
w Saving

1

2
4
tomcatv

1

2
4
swim
benchmark

1

2
applu

4

Fig. 8. Energy in fastest execution mode

4

Performance evaluation

This section describes the performance of OSCAR multigrain parallelizing compiler with the proposed power saving scheme. The evaluation are performed byusing the static scheduler in the compiler. For this evaluation, the parameters
for frequencies, voltages, dynamic energies, and static powers shown in Table
1 are used. In this paper, only energy for processors was evaluated. The statetransition overhead with frequency, dynamic and static power is shown in Table
2. The dynamic power at FULL frequency is measured by using Wattch[18].
Cooperative Voltage Scaling[19] is vebered to determine the parameters like thetransition overhead, attribute of voltage/frequency and dynamic power at MID
and LOW frequency. Application programs, such as applu, tomcatv and swim
from SPEC95 CFP, are used in the evaluation. For applu, inline expansion andloop aligned decomposition for the data localization[12] are applied. Also, themain loop in applu is divided into the static part without conditional branch
and the dynamic part with branches, in order to apply the proposed scheme.
4.1

Performance in the fastest execution mode

Figure 7 shows the speedup ratio of each program, and Figure 8 shows the totalenergy consumption for 1, 2 and 4 processors in the fastest execution mode. In
these graphs, the left bars represents the results of OSCAR compiler without the
proposed power saving scheme, the right bars show the results of OSCAR compiler using the proposed scheme. As shown in Figure 7, there is no performancedegradation by using the power saving scheme in the fastest execution mode,
while the energy consumption is reduced as shown in Figure 8. The proposed
scheme reduced the consumed energy by 36.3 %(from 102[J] down to 65.0[J]) for
2 processors, 60.7 %(from 174[J] down to 68.4[J]) for 4 processors in SPEC95
applu, 1.56 %(from 92.1[J] down to 90.6[J]) for 2 processors, 4.64 %(from 95.0[J]down to 90.6[J]) for 4 processors in tomcatv.

speedup ratio

4.5
4
3.5
3
2.5
2
1.5
1
0.5
0

w/o Saving
w Saving

1

2
tomcatv

4

1

2
4
swim
benchmark

1

2
applu

4

Fig. 9. Speedup in deadline mode

The reason why the proposed scheme can not reduce the energy consumption
in tomcatv and swim is that the both application programs have large parallelism
and the all processors must execute in “FULL” mode to attain the minimum
execution time. The parallel execution time of these programs with 4 processors
is about one quarter of sequential execution time. Therefore, though the power
consumption is quadrupled by using 4 processors, the total energy consumption
is almost equal to the energy of sequential execution.
On the other hand, there is a certain amount of idle time in applu. Therefore,
the following controls were made. Figure 6 shows the main loop to which thepower saving scheme is applied for 4 processors. The DOALL6, LOOP10-13,
DOALL17, LOOP18-21, DOALL22 had no margin, then their frequencies were
set to FULL. MID or LOW was chosen for other MTs according to each marginof task. Furthermore, the proposed scheme shut off the power supply in the idle
times.
4.2

Performance in real-time processing with deadline constraints

Next, the evaluation results of real-time execution mode with the deadline constraint are described. Figure 9 shows the speedup ratio and Figure 10 shows
the total energy consumption with the real-time deadline that was set to equal
to the sequential execution time. The speedup ratio could be kept almost 1, asshown in Figure 9. This means the proposed scheme could satisfy the deadline
constraints, or the sequential processing time.
Figure 10 shows that the saved power for real-time processing mode were
37.8 %(from 102[J] down to 63.3[J]) for 2 processors, 62.2 %(from 174[J] down
to 65.8[J]) for 4 processors in applu, 21.6 %(from 92.1[J] down to 72.2[J]) for 2
processors, 45.4 %(from 95.0[J] down to 51.9[J]) for 4 processors in tomcatv, and23.7 %(from 103[J] down to 78.7[J]) for 2 processors, 46.5 %(from 103[J] down
to 55.2[J]) for 4 processors in swim.

energy(J)

200
180
160
140
120
100
80
60
40
20
0

w/o Saving
w Saving

1

2
4
tomcatv

1

2
4
swim
benchmark

1

2
applu

4

Fig. 10. Energy in deadline mode

These results shows the proposed scheme could realize large power reduction
for programs with large parallelism under the real-time execution mode.

5

Conclusions

This paper has proposed compiler control power saving scheme for multi core
processors. The proposed scheme can be applied for both the fastest parallel
executing mode and the real-time execution mode with deadline constraint. The
scheme gives us good effective performance and low energy consumption for theboth modes.
The evaluation using OSCAR multigrain parallelizing compiler has shown
the proposed scheme gave 60.7 percent energy savings for SPEC CFP95 applu
using 4 processors without the performance degradation, and 45.4 percent energy
savings for SPEC CFP95 tomcatv using 4 processors with real-time deadline
constraint, or the sequential processing time, and 46.5 percent energy savings
for SPEC CFP95 swim using 4 processors with the deadline constraint.
The detailed evaluation using an actual multi core processor and the implement of the dynamic scheduling are the future works.
Acknowledgments
A part of this research has been supported by NEDO “Advanced HeterogeneousMultiprocessor”, STARC “Automatic Parallelizing Compiler Cooperative Single
Chip Multiprocessor” and NEDO “Multi core processors for real time consumer
electronics”.

References
1. M.Wolfe. High performance compilers for parallel computing. Addison-Wesley
Publishing Company, 1996.

2. R. Eigenmann, J. Hoeflinger, and D. Padua. On the automatic parallelization of
the perfect benchmarks. IEEE Trans. on parallel and distributed systems, 9(1),Jan. 1998.
3. M. W. Hall, J. M. Anderson, S. P. Amarasinghe, B. R. Murphy, S. Liao, E. Bugnion,
and M. S. Lam. Maximizing multiprocessor performance with the suif compiler.
IEEE Computer, 1996.
4. Marc Gonzalez, Xavier Martorell, Jose Oliver, Eduard Ayguade, and Jesus
Labarta. Code generation and run-time support for multi-level parallelism exploitation. In Proc. of the 8th International Workshop on Compilers for Parallel
Computing, Jan. 2000.
5. H. Honda, M. Iwata, and H. Kasahara. Coarse grain parallelism detection schemeof a fortran program. Trans. of IEICE, J73-D-1(12):951–960, Dec. 1990.
6. H.Kasahara and et al. A multi-grain parallelizing compilation scheme on oscar.
Proc. 4th Workshop on Language and Compilers for Parallel Computing, 1991.
7. Hironori Kasahara. Advanced automatic parallelizing compiler technology. IPSJMAGANIE, Apr 2003.
8. David H. Albonesi and et al. Dynamically tuning processor resources with adaptive
processing. In IEEE Computer, Dec. 2003.
9. Q. Wu, P. Juang, M. Martonosi, and D. W. Clark. Formal online methods forvoltage/frequency control in multiple clock domain microprocessors. In EleventhInternational Conference on Architectural Support for Programming Languages andOperating Systems, Oct. 2004.
10. Chung-Hsing Hsu and Ulrich Kremer. The design, implementation, and evaluation of a compiler algorithm for cpu energy reduction. In The ACM SIGPLAN
Conference on Programming Language Design and Implementation, Jun. 2003.
11. M. Obata, J. Shirako, H. Kaminaga, K. Ishizaka, and H. Kasahara. Hierarchicalparallelism control for multigrain parallel processing. In Proc. of 15th International
Workshop on Languages and Compilers for Parallel Computing, Aug. 2002.
12. K. Ishizaka, T. Miyamoto, M. obata J. Shirako, K. kimura, and H. Kasahara.
Performance of oscar multigrain parallelizing compiler on smp servers. In Proc. of
17th International Workshop on Languages and Compilers for Parallel Computing,Sep. 2004.
13. Jun shirako, Kouhei Nagasawa, Kazuhisa Ishizaka, Motoki Obata, and Hironori
Kasahara. Selective inline expansion for improvement of multi grain parallelism.
PDCN2004, Feb. 2004.
14. H. Kasahara, H. Honda, M. Iwata, and M. Hirota. A compilation scheme for macrodataflow computation on hierarchical multiprocessor system. Proc. Int Conf. on
Parallel Processing, 1990.
15. H. Kasahara, S. Narita, and S. Hashimoto. Architecture of oscar. Trans of IEICE,
J71-D(8), Aug. 1988.
16. H. Kasahara, H. Honda, and S. Narita. Parallel processing of near fine grain tasks
using static scheduling on oscar. Proceedings of Supercomputing ’90, Nov. 1990.
17. K. Kimura, W. Ogata, M. Okamoto, and H. Kasahara. Near fine grain parallel
processing on single chip multiprocessors. Trans. of IPSJ, 40(5), May. 1999.
18. David Brooks, Vivek Tiwari, and Margaret Martonosi. Wattch: A framework forarchitectural-level power analysis and optimizations. In Proc. of the 27th ISCA,
Jun. 2000.
19. Hiroshi Kawaguchi, Youngsoo Shin, and Takayasu Sakurai. uitron-lp: Powerconscious real-time os based on cooperative voltage scaling for multimedia applications. In IEEE Transactions on multimedia, Feb. 2005.