1943-0663 (c) 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/LES.2016.2519521, IEEE Embedded Systems Letters

IEEE EMBEDDED SYSTEMS LETTERS, VOL. 13, NO. 9, SEPTEMBER 2015 1

Extending Amdahl’s Law for Heterogeneous Multicore Processor with Consideration of the

Overhead of Data Preparation Songwen Pei, Member, IEEE, Myoung-Seo Kim, Student Member, IEEE, Jean-Luc Gaudiot, Fellow, IEEE

Abstract—We extend Amdahl’s law by considering the Over- head of Data Preparation (ODP) for multicore systems, and apply it to three “traditional” multicore system scenarios (homoge- neous symmetric multicore, asymmetric multicore, and dynamic multicore) and two new scenarios (heterogeneous CPU-GPU multicore and dynamic CPU-GPU multicore). It demonstrates that potential innovations in heterogeneous system architecture are indispensable to decrease ODP.

Index Terms—Amdahl’s Law, Heterogeneous Systems, Perfor- mance Evaluation, Speedup Model, Overhead of Data Prepara- tion

I. INTRODUCTION

A S multicore processors have become mainstream, it hasbecome crucial to identify performance bounds and performance scaling properties in exploiting the massive par- allelism they offer [1]. Besides, processor design has been transiting from the homogeneous multicore model to the heterogeneous model [2]. Furthermore, energy efficiency and scalability are affected by the power constraints imposed on heterogeneous processors [3]. The memory wall [4] and com- munication issues will continue increasing the gap between the performance of an ideal processor and that of a “prac- tical” processor. Therefore, the overhead of data preparation becomes an unavoidable key parameter. Assume that a fraction f of a program’s execution is infinitely parallelizable without scheduling and synchronizing overhead with c processors (cores), while the remaining fraction 1-f is assumed to be sequential execution. Then, the computational speedup of the system is governed by the well-known equation (Amdahl’s law [5, 6]):

SA(f,c) = 1

(1−f) + f c

(1)

The equation is correct as long as three key assumptions are verified: (1) the programs to be executed are of fixed-size and the fraction of the programs that is parallelizable remains constant as well; (2) there exists an infinite memory space without extra overhead of switching memory blocks and disk

Songwen Pei is with Shanghai Key Lab of Modern Optical Systems, University of Shanghai for Science and Technology, Shanghai, 200093 China and also with Parallel Systems and Computer Architecture Lab, University of California, Irvine, CA, 92697 USA. e-mail: [email protected]

Myoung-Seo Kim and Jean-Luc Gaudiot are with Parallel Systems and Computer Architecture Lab, University of California, Irvine, CA,92697 USA (e-mail: {myoungseo.kim, gaudiot}@uci.edu). Myoung-Seo Kim is also a corresponding author.

Manuscript received June 15, 2015; revised July 17, 2015.

blocks, etc., and (3) the overhead of preparing the data to be used by computing units, which includes memory access, com- munication on-chips or off-chips and synchronization among cores, can be neglected. In practical multicore systems, as it turns out, the overhead of data preparation is between 30% and 90% of the total execution time depending on the kind of application considered [7]. In other words, the overhead of transferring data between CPUs and GPUs in a heterogeneous multicore system could be the bottleneck of high performance computing. As we introduce this parameter in the single- threaded multicore system, we propose a set of equations in the following sections.

II. REVISITING SPEEDUP MODEL BY CONSIDERING THE OVERHEAD OF DATA PREPARATION (ODP)

As proposed by Hill & Marty [6], we first assume that a multicore chip of a given area and manufacturing technology is composed of at most n Base Core Equivalents (BCEs) (a single BCE implements a baseline core). Then, we assume that the resources of r BCEs can be used to create a powerful core with sequential performance perf(r), while the performance of a single-BCE core is 1 [6]. perf(r) is an arbitrary function, where 1< perf(r) <r.

Since an improvement in sequential performance by mi- croarchitecture techniques alone would follow Pollack’s rule [8], perf(r) is roughly proportional to the square root of the increase in complexity. At the same time, because of the “memory wall,” the overhead of preparing the data and accessing the memory, of transmitting data on- and off- chip, of transferring data between CPU memories and GPU mem- ories for heterogeneous system, of synchronizing processes, etc., becomes so significant that it cannot be ignored any longer. However, Amdahl’s law only considers the cost of instruction execution. We will thus now assume that the whole cost of executing a program can be split into two independent parts, one is preparing the data for execution and the other one is running instructions when the required data are ready. Therefore, the Overhead of Data Preparation (ODP) includes the cost of preparing data for execution, to the exclusion of actual execution. As shown in Figure 1, ODP can be considered to produce a new speedup equation; we will call it the “Extended Amdahl’s law” as expressed in equation (2):

SEA(fc,c,pc) = 1

((1−fc) + fcc ) ·pc + (1−pc) (2)

IEEE EMBEDDED SYSTEMS LETTERS, VOL. 13, NO. 9, SEPTEMBER 2015 2

Fig. 1. Normalized task (equivalence time). Split between Computation and Data Preparation.

where pc denotes the computation portion, 1 − pc denotes the Data Preparation portion normalized to the computation portion: since the clock frequencies and the ISAs of CPUs, GPUs, off-chip bus and memory arbitrator would likely be different, we should normalize the performance of Data Prepa- ration instructions to that of computing instructions. The fc is the parallelizable computation portion, 1−fc is the sequential computation portion.

As shown in Figure 1, however, equation (2) does not make allowance for the introduction of hardware techniques that would decrease or eliminate the overhead of data preparation. We can further divide the portion of data preparation into three sub-parts: 1−fh, αfh and (1−α)fh. 1−fh denotes the portion of data preparation which is closely dependent on computing instructions. fh denotes the data preparation portion of the program that can be overlapped with “computing” instructions before introducing advanced techniques, where 0 ≤ fh ≤ 1.

Memory access instructions generally can be executed si- multaneously with independent computing instructions. How- ever, it will not be possible to execute all of the data preparation instructions simultaneously with computing in- structions. Further, not all operations of data preparation would be executed with computing instructions according to our observations. For example, if a load instruction is independent of the following computing instructions, it can be issued simultaneously with them. While it would not be issued if the queue of issuing load instructions was full.

Hence, we introduce the parameter α to denote the per- centage of data preparation instructions which are actually executed simultaneously with computing instructions before using advanced architectural techniques (0 ≤ α ≤ 1). Thus, αfh denotes the portion of actual parallelized instructions for data preparation and (1 − α)fh denotes the portion of data preparation instructions which cannot be overlapped with computing instructions without sophisticated architecture techniques.

With the help of advanced architectural techniques such as data prefetching, speculative execution, universal memo- ry, no-copy data transfer, 3D NoC, etc., (1 − α)fh could be decreased significantly. Thus, we further introduce the variable kc to model what percentage of data preparation cannot be overlapped on a c cores system by using new advanced techniques (0≤ kc ≤ 1). After normalization to the computation part in theory, the portion of data preparation instructions which cannot be overlapped on a c core system becomes fud = (1 − fh) + kc · (1 − α)fh. Assuming that the execution time of parallelizable data preparation is less than the execution time of computation and the serial data preparation time put together, the portion of parallelizable data preparation can be masked by computation and serial data

preparation. Therefore, we can extend Amdahl’s law to the following Enhanced Amdahl’s law:

S ′

EA(fc,c,pc,fud) = 1

((1−fc)+ fcc )pc+fud(1−pc) (3)

III. CASE STUDIES OF OUR ENHANCED AMDAHL’S LAW SPEEDUP MODEL

As in Hill & Marty [6], we also assume that a multicore chip of a given area and manufacturing technology is composed of n Base Core Equivalents (BCEs). Assumed that, if we consider only hardware techniques, the improved sequential performance obeys Pollack’s rule [7], perf(r) is approximate- ly proportional to the square root of the increasing size of a chip or number of transistors. For simplicity, we also assume that the performance (cost) of data preparation is also roughly proportional to perf(r).

A. Homogeneous Symmetric Multicore

We follow Hill & Marty’s [6] definition of a symmetric mul- ticore architecture and assume that a homogeneous symmetric multicore chip uses one single-BCE core with r BCEs to execute sequentially at performance perf(r), and that it uses all c = n/r cores to execute in parallel at performance perf(r) · n/r. Note that performance is driven by the execution time of a given program on a processor which is only dependent on the technology of the microarchitecture. Therefore, we obtain the following speedup equation for a homogeneous symmetric multicore architecture:

ShsEA = 1

( 1−fc

perf(r) +

fc·r perf(r)·n )pc+

fud perf(r)

(1−pc) (4)

Figure 2 assumes a symmetric multicore chip with a maximum number n=256 of BCEs and perf(r) =

√ r. The x-axis

presents the number of resources (BCEs) to be configured into a core/processor with a total budget of 256 BCEs. For example, if x=4, it means that each single core uses 4 BCEs and that it has a total of 64 cores with 4 BCEs each, for a total budget of 256 BCEs resources. The y-axis shows the speedup compared to the baseline of a single-BCE baseline core. We further assume a parameter(pc) with different values for the portion of computation in a program. For instance, pc can be 0.2, 0.4, 0.6, and 0.8. In addition, it can be overlapped with data preparation (fh=0.2, 0.4, 0.6, 0.8), and also different values for the parallel fractions in the portion of the computation (fc=0.5, 0.9, 0.975, 0.99, 0.999). We choose a representative (pc = 0.6,fh = 0.8) from 80 similar curve trends as example in the following subsections.

We performed experiments on the Gem5-GPU simulator [9] which is a standard simulator of heterogeneous systems and tested backprop, bfs, mum, and hs in the Rodina benchmark [10]. The configuration parameters of simulator is accordant to [11]. We found that the average percentage of sequential load/store operations is about 1/3. Incidentally, we got some similar supportive evidences from other research results. The floating-point operation(fpop) of 052.alvinn which belongs to the CFP92 benchmark in the SPEC suite makes up 27.6% of all the operations, memory operations 48.3%, branch opera- tions 5.1%, while others (total-memory-fpop-branch) make up

IEEE EMBEDDED SYSTEMS LETTERS, VOL. 13, NO. 9, SEPTEMBER 2015 3

Fig. 2. Speedup Distribution of Homogeneous Symmetric Multicore where pc = 0.6, fh = 0.8

Fig. 3. Speedup Distribution of Homogeneous Asymmetric Multicore where pc = 0.6, fh = 0.8

18.9% [12]. Thus, the summary percentage of computation is only 27.6%, and the remaining percentage of operations which are relevant to data preparation is about 72.3%. Therefore, we empirically set kc and α to 1/3 and 2/3 respectively. It means that, in a given application, 1/3 of data preparation cannot be actually executed in parallel, while 2/3 of data preparation can take place in parallel with computation and other data preparation operations.

As shown in Figure 2, the speedup will vary with the number of BCEs and reaches the maximum 56.71 when r = 16 BCEs, and fc = 0.999. This means that almost 60% of the instructions in a program are parallelizable “computing” instructions, while the remaining 32% are data preparation instructions pertaining to memory access, data transfer, etc. which can be masked.

B. Homogeneous Asymmetric Multicore

Just as the example proposed by Hill & Marty [5], a homogeneous asymmetric multicore chip is composed of one large core with r BCEs, and the remaining of other n−r BCEs with the same Instruction set architecture (ISA). Assuming that the serial computing part is executed by one large core and the parallel computing part is executed by the remaining n−r one- BCEs cores and the large core simultaneously, the modified Amdahl’s law with consideration of the ODP becomes:

ShaEA = 1

( 1−fc

perf(r) +

fc perf(r)+n−r )pc+

fud perf(r)

(1−pc) (5)

As shown in Figure 3, the maximum speedup is 70.12 with r = 128 BCEs and fc = 0.999. It is higher than

the maximum speedup 56.71 shown in Figure 2. In general, the homogeneous asymmetric architecture has a potential higher speedup performance. Furthermore, comparing to the homogeneous symmetric architecture, a more powerful core should be built with 128 BCEs to achieve the highest possible speedup in an asymmetric architecture. Further, the maximum speedup with consideration of ODP is almost twice that of a traditional asymmetric architecture. A full length paper will include details.

C. Homogeneous Dynamic Multicore

Based on the same assumption as that for a dynamic multicore in [5], the serial part of a program can be executed by a large core dynamically combining up to r single-BCEs by utilizing some advanced techniques (e.g., thread-level specula- tion, helper threads, data prefetching). On the other hand, the parallelizable part is executed by all n base cores with dynamic scheduling techniques such as simultaneous multithreads, dy- namic instructions schedules, etc. The modified Amdahl’s law with consideration for ODP thus becomes:

ShdEA = 1

( 1−fc perf(r)

+ fc n )pc +

fud perf(r)

(1−pc) (6)

Based on equation 6, we find that the highest possible speedup is 106.57 for a homogeneous symmetric and dynamic multicore architecture where r = 256 and fc = 0.999. Because it uses ideal dynamic techniques to increase proces- sor performance, the performance will rise directly with the number of cores. Since the dynamic techniques are assumed to eliminate all the overhead from data hazards, control hazards and resource hazards, without considering the overhead caused by these dynamic techniques, the maximum performance improvements are higher than that in homogeneous symmetric architectures.

D. Heterogeneous CPU-GPU Multicore

Just as a homogeneous asymmetric multicore,some cores may be more powerful than others. The more powerful cores are built as CPU processors, and the others are built as GPU cores. Note that the assumption of single-BCE is equivalent to a GPU core here rather than CPU core, if we consider the chip area of a single-BCE core, and a powerful CPU processor is composed of i CPU cores where each one comprises r BCEs. We assume that i CPU processors handle all serial computing at performance i ·perf(r). The remaining n− ir BCEs are equivalent to n− ir GPU cores, and all the GPUs cores and CPU processors cooperatively execute the parallel portion of the program. In the same manner we calculate the computational performance, thus we assume that the serial performance of data preparation is proportional to the amount of resources (number of BCEs) on the chip by a factor perf(r). Consequently, we obtain the speedup equation (7) below:

S cg EA =

( 1−fc

i·perf(r)+ fc

i·perf(r)+n−i·r )pc+ fud

perf(r) (1−pc) (7)

As shown in Figure 4, the highest speedup is 40.58 where

IEEE EMBEDDED SYSTEMS LETTERS, VOL. 13, NO. 9, SEPTEMBER 2015 4

Fig. 4. Speedup Distribution of Heterogeneous CPU-GPU Multicore where pc = 0.6, fh = 0.8, i = 4

Fig. 5. Speedup Distribution of Heterogeneous Dynamic CPU-GPU Multi- core where pc = 0.6, fh = 0.8, i = 4

r = 32 and fc = 0.999. In other words, the highest per- formance heterogeneous CPU-GPU architecture is composed of one CMP with 4 CPU cores, and each CPU core has 32 BCEs. The remaining 128 BCEs are built as 128 GPU cores. However, the highest speedup is less than that of homogeneous asymmetric architecture although the CPU processor also uses 128 BCEs.

E. Heterogeneous Dynamic CPU-GPU Multicore

Similarly to the homogeneous dynamic multicore, we can derive an equation for a heterogeneous dynamic CPU-GPU multicore.While it can also schedule all the computation resources, just as what was assumed in [5], n base cores can also execute in parallel either CPUs or GPUs cores. Further, it should be noted that we also assume the cost of data preparation to be the same as that in the general heterogeneous CPU-GPU model. Therefore, the equation becomes:

S cgd EA =

( 1−fc i·perf(r) +

fc n )pc +

fud perf(r)

(1−pc) (8)

IV. CONCLUSION

When one takes into account the overhead of data prepa- ration (ODP), the speedup will not grow linearly with the number of cores. Furthermore, a heterogeneous CPU-GPU architecture would be more beneficial than a homogeneous architecture according to the comparison curves of speedup distribution.

This is a quantitative analysis strictly based on a theoretical and general model. To some extent, however, we have been able to compare the results with Hill’s theoretical approaches for multicore architectures. We would also compare it with other works in a regular paper. Further research will entail investigating the energy efficiency of multicore processors and multithread processors.

ACKNOWLEDGMENT

We would like to thank the anonymous reviewer- s for their invaluable comments. This work was par- tially funded by the Shanghai Municipal Natural Sci- ence Foundation(15ZR1428600) and the National Science Foundation(XPS-1439097).

REFERENCES

[1] H.Che, and M.Nguyen, “Amdahl’s Law for Multithreaded Multicore Processors”, International Journal of Parallel Distributed Computing, vol.74, no.10, pp.3056-3069, Jun. 2014.

[2] P.Rogers, “Heterogeneous System Architecture Overview”, in Proc. of Hot Chips Sym., Aug. 2013.

[3] A. Marowka. “Extending Amdahl’s Law for Heteroge- neous Computing”, in Proc. of Sym. on Parallel and Dis- tributed Processing with Applications,2012,pp.309-316.

[4] X.H.Sun, Y.Chen, ”Reevaluating Amdahl’s law in the multicore era”, Journal of Parallel and Distributed Com- puting,vol.70,no.2, pp.183-188, 2010.

[5] G.M.Amdahl, “Validity of the Single-Processor Approach to Achieving Large-Sclae Computing Capabilities”, in Proc. of the American Federation of Inf. Processing Soci- eties(AFIPS), 1967, pp.483-485.

[6] M.D.Hill,M.R.Marty,“Amdahl’s Law in the Multicore Er- a”,Computer, vol.41,no.12,pp.24-31,2008.

[7] M.Daga, A.M.Aji, W.Feng, ”On the Efficacy of a Fused CPU+GPU Processor (or APU) for Parallel Computing”, in Proc. of the Sym. on App. Acc. in High-Perf. Comput- ing(SAAHPC),2011, pp.141-149.

[8] F.Pollack, “New Microarchitecture Challenges in the Coming Generations of CMOS Process Technolo- gies”, in Proc. of the Intl. Sym. on Microarchitec- ture(MICRO),1999, pp.2.

[9] J.Power, J.Hestness, M.S.Orr, et al. “gem5-gpu: A Het- erogeneous CPU-GPU Simulator”, Computer Architecture Letters,vol.13,no.1,pp.1-4,2014.

[10] S.Che, M.Boyer, J.Meng, et al. “Rodinia: a benchmark suite for heterogeneous computing”, in Proc. of the Sym. Workload Characterization,2009,pp.44-54.

[11] S.Pei, M.Kim, J.Gaudiot, et al. “Fusion Coherence: Scalable Cache for Heterogeneous Kilo-core System”, in Proc. of the Annual Conf. of Advanced Computer Architecture,2014,pp.1-15.

[12] Kaivalya, M.Dixit,“Overview of the SPEC Benchmark- s”, The Benchmark Handbook, Ch.9, Morgan Kaufmann Publishers, 1998.

View publication statsView publication stats

https://www.researchgate.net/publication/291333489