日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

A High-throughput Computing Scheme on
Many-core Processors
Yiqing Zhu

Shunsuke Takano

Mizuki OkaKazuhiko KatoWei ChenThis paper proposes a high-throughput computing scheme for many-core processors: cave and court computing (CCC). To achieve high concurrency, this scheme allows data inconsistency in order to perform lock-freeoperations in the cave mode and merge the results to solve the data inconsistency in the court mode. Thescheme supports applications demanding high throughput such as big-data processing. We study CCC withB-Tree to perform a simple big-data process: counting the occurrence of each word. By evaluating theresult, we show this scheme has an acceptable performance and specific scalability. We argue that given
careful implementation, the CCC scheme is competent for high-throughput computing.

scheme, threads process data in private memory

1 Introduction

without any data synchronization in the cave mode,

Recently, big-data researchers have mainly fo-to increase concurrency, and merge the results into

cused on how to scale out big-data processing acrosspublic memory to solve data inconsistency in thea large number of servers.

However, big-data-court mode. During the execution, CCC switchesoriented software schemes for high-throughput

between cave mode and court mode. Combining

computing on a single computer have not been

the CCC scheme with an appropriate data struc-studied much. Making good use of many CPUs has

ture such as B-Tree supports high concurrent op-

become an important issue since processor industry

erations. We propose this novel scheme greatly in-is experiencing a transition from the exponential

creases the use of many-core, thus achieving highincrease in per-core CPU speed to the exponential

throughput, making the scheme appropriate forincrease in the number of cores. By taking advan-

big-data processing.

tage of many-core, we believe applying thread-level

The rest of the paper is organized as follows.

parallel processing in a single server obviously en-

In Section 2, the research background and related

joys many benefits such as lower complexity andwork are introduced. In Section 3, a brief intro-lower price.

duction is given to the preliminary knowledge. InIn this paper, we propose a high-throughput pro-Section 4, an overview of CCC is provided, while

cessing software scheme on many-core, which wein Section 5, the CCC implementation on B-Treecall cave and court computing (CCC). In our CCC

is described. In Section 6, the experiment results
are presented. In Section 7, the paper is concluded

A High-throughput Computing Scheme on Many-core
Processors
Zhu, Takano, Chen, Oka, Kato, , Dept. of Information and Computer Science, University of Tsukuba.

and future work is discussed.

can perform competitively with those written with

2 Background and Related WorkPthreads. Further work on Phoenix like [9] andThe amount of data has been exploding. Ana-[3] provided diﬀerent optimization on it.

Otherlyzing big data, is becoming an inscreasingly im-MapReduce implementation such as Mars [6] shows

portant basis of competition.

Since big data isthat an implementation on GPU is also an alter-

very large and complex, it requires many techniques

native choice to cluster-based MapReduce. In ad-and experiments to process. A common solution

dition to MapReduce, other GPU-focused studies

in industry recently is to scale out big-data pro-

provide other models or schemes on the GPU for

cessing among a large number of servers because

data processing.

the computational ability of a single computer islimited.

Many mature programming models orschemes have been proposed. For example, MapReduce [4], which was first developed by Google in2004, is based on thisscaling outapproach.

3 Preliminary
3. 1 Concurrency Control Mechanisms in
Shared Memory
The traditional concurrency control mechanism

In the last decade, the processor industry has

in shared memory can be mainly divided into twoexpanded. The increase in computational ability

categories: the pessimistic approach and the op-

makes it theoretically possible to process big datatimistic approach. A well-known example of theon a single server. The benefits are obvious, suchpessimistic approach is the lock. In the lock-based

as lower computational complexity and lower main-

method, data consistency is always maintained dur-tenance cost. However, the per-core CPU speed ising execution, by blocking the threads that may

reaching a physical limit, as Herb Sutter stated incause data inconsistency. The optimistic approach,2005 [8], which indicates this increase cannot be

for example, software transactional memory [5], as-translated directly into faster computation. Mean-sumes multiple threads can be completed without

while, increasing the number of cores exponentiallyaﬀecting each other. After a piece of code is exe-is the current focus of the processor industry rather

cuted, the transactional memory library checks thethan the pursuit of faster per-core speed.

data consistency and rolls back if it finds inconsis-Thischange had a profound impact on software performance, which reaps the benefits of multicores.

tent data.
Unfortunately,

neither approach oﬀers highTherefore the traditional multi-thread approach isthroughput on many-core computers. The limita-

worth a second look for big-data processing jobs.

tion of the pessimistic approach is that it blocks

Parallelizing the big-data process requires very

threads thus decreasing the concurrency; the lim-

high throughput to keep the process within a tolera-

itation of the optimistic approach is that when it

ble time. In thread-level parallelizing, concurrency

finds inconsistent data, it has to roll back, which isoccurs in the shared memory.

a big waste.

High-throughput

concurrency control requires important features.
For example, the concurrency should be extremely

3. 2 B-Treehigh, no rollback or wasted work occurs if possible,

B-Tree is a type of balanced tree in indexing

and little copying memory if possible.

data structure, which eﬃciently supports opera-

A MapReduce library in shared memory such as

tions, such as search, insertion or deletion, in loga-Phoenix [7] demonstrated the MapReduce model

rithmic time. B-Tree was first introduced by Bayer図1

An example of a B-Tree of order 6.

and McCreight [1] and is often used to store data

data processing, people seldom care about interme-in secondary storage to reduce disk I/O. A notable

diate conditions. Since the scope of big-data pro-

property of B-Tree is that all leaf nodes are in thecessing is much smaller, we can allow data inconsis-

same level. Figure 1 shows a typical B-Tree of ordertency to occur during the execution. Without data

6, where keys are represented as integers.

synchronization, very high concurrency is possible.
Then the inconsistency is solved, that is the results
are merged from asynchronous computing, to get asynchronized state.
Our main idea comes from the concept calledcave and courtin an oﬃce design. The term“cave” means a private working area for every individual in an oﬃce; “court” a means public meeting or discussion area. In design, an oﬃce with“cave and court” is a good design. This concept isbased on the characteristics of human cooperation.
We propose cave and court computing scheme, applying this method of cooperation to one of thethreads.
図2

Overview of the cave and court
computing scheme.

Cave and court computing has two execution
modes, the cave mode and the court mode.

Inthe cave mode, every thread performs normal operations high-concurrently without any data syn-

4 Cave and Court Computing Scheme

chronization, saving the results in private regions.

The limitation of traditional approaches comes

Most of the time, the threads are in the the cavefrom the fact that the pessimistic approach andmode. In the court mode, the threads do not per-the optimistic approach require extra work to han-form normal operations, but merge the results indle data consistency. Whether blocking threads or

the private regions. Execution switches between

rolling back, these two approaches try to maintainthe cave mode and the court mode during the ex-in a data-consistent condition. However, in big-ecution. The cave-court circle loops hundreds orthousands of times in a processing application, pro-

The splitting strictly follows B-Tree semantics butcessing data asynchronously with high throughput

performs diﬀerently with normal B-Tree because

in the cave mode and then merging the results inthere can be many keys in the private region suchthe court mode. The merged results in the courtthat the original node may split into more than twomode can be used for future computation in thenodes. Concurrent reorganization is possible andnext circle.

necessary for high throughput. However the tradi-

5 Cave and Court Computing with BTreetional lock algorithm [2] on B-Tree cannot maintainhigh throughput, because so many new leaf nodes

Unlike MapReduce, which only works on a par-must be produced that reorganization on a leaf

ticular data structure, the key/value pair, the CCC

node may aﬀect very upper-level internal nodes, orscheme can be easily combined with commonly usedeven the root. As a consequence, the locks on thedata structures. In this research, we implement theupper-level nodes are diﬃcult to release.

CCC scheme with B-Tree.

In the court mode, almost all the node in the B-Figure 3 shows the structure of the cave and court

Tree are modified and many internal nodes would

computing with B-Tree. Diﬀerent from standard

be modified more then once due to the large amount

B-Tree, in each leaf node, there are separate pri-of splitting in their children. To improve the con-vate regions for each thread. The private regions

currency and eﬃciency, we use a bottom-up method

are invisible to other threads, so that, in the cave

to perform an ”accumulating” reorganization levelmode, threads perform read operations throughout

up level rather than node-by-node reorganization

the whole tree and write operations only in one sseparately. In detail, all the nodes in the same

shared mmory even though data inconsistency may

level are reorganized at the same time, thus merg-occur in the cave mode.

ing keys and splitting nodes without modification

Search: In search, a thread searches the pub-on the parents. After this level is completed, thelic memory, which includes the internal nodes andnew produced nodes are used for reorganization in

public regions of the leaf nodes, as well as the pri-next level up to it.

vate regions corresponding to the thread in the leaf

6 Experimentsnodes.
Insert: In insertion, a thread finds the proper

We apply our CCC scheme to process big data

leaf node according to the B-Tree semantics. Theon a rather simple example: the word count. Thethread inserts the key into the private region in thisword-count program counts the occurrence for eachleaf node. The new keys are merged in the public

word in a big file. The key/value pairs of (word,region in the court mode.

count) are stored in the cave and court B-Tree inIn the court mode, threads pause normal operations to merge the results in each leaf node. We
name this operation

reorganize .

sorted order. The B-Tree acts as the index of words
occurring.
We perform our experiment on a Dell PowerEdge

Reorganize: In reorganization, keys both in theR815. It has four 16-core 2.1GHz AMD Opeteron

private regions and the public region of one node

6272 processors, that is, 64 cores in total, and 64G

are sorted together and then put in the node. Sim-memory. We used the Wikipedia English version

ilar to the normal insert operation on standard B-

data with all the non-alphanumeric characters re-Tree, nodes may split because of node overflow.

moved. The data is about 36G.

図3

Structure of the cave and court computing with B-Tree.

Figure 4 is the experimental result. The x-axis isdata processing. We first introduced the basic con-the number of threads and the y-axis is the time

cept of the CCC scheme. Then we introduced ourrequired to complete the task. The word count

CCC implementation with B-Tree, as the search,

job can be completed in about 30 minutes, an ac-insertion and reorganization algorithm. Finally, weceptable result considering the lower computational

performed a word count experiment on Wikipedia

complexity and maintenance cost compared to pro-data.

cessing data across a large number of servers, typ-The current experimental results shows theically on a cluster-based MapReduce implementa-

scheme scales out until the number of threads istion. However, the performance peaks when theequal to 24 and saturates when the number isnumber of threads exceeds 24. One possible bottle-

greater than 24.

necks originates from the IO bandwidth. That is,I/O bandwidth limitation.

in the cave mode, threads perform lock-free opera-

will examine our implementation more closely totions so fast that they have to wait for the read-filecheck whether there is room for achieving a better

thread to fill in the input buﬀer.

performance. Last, we want to compare our soft-

We assume this is due to theIn future work, We

7 Conclusion and Future Workware scheme to the Amazon Elastic MapReduce
service †1 with the same instance number as ourIn this paper, we propose a novel software scheme

core number to test if our proposed scheme is an

on many-core processors called cave and court com-alternative choice to MapReduce for big-data pro-puting (CCC). By switching between the cave modecessing.

and the court mode, this scheme allows data inconsistency in order to perform lock-free operations in

参 考 文 献the cave mode, and merge the results to solve the[1] Bayer, R. and McCreight, E.: Organization andmaintenance of large ordered indexes, Springer,

data inconsistency in the court mode. The scheme
supports high throughput applications such as big-†1 http://aws.amazon.com/jp/elasticmapreduce/

6000

total
court
cave

5000

time(s)

4000
3000
2000
1000
008

1624324048566472

number of threads
図4

Wordcount time cost on English Wikipedia (36G). The “total” is the total time cost and the“cave” and the “court” are the cave mode time and court mode time, respectively.

2002.
[2] Bayer, R. and Schkolnick, M.: Concurrency ofoperations on B-trees, Acta informatica, Vol. 9,
No. 1(1977), pp. 1–21.
[3] Chen, R., Chen, H., and Zang, B.: TiledMapReduce: optimizing resource usages of dataparallel applications on multicore with tiling, Proceedings of the 19th international conference onParallel architectures and compilation techniques,
PACT ’10, New York, NY, USA, ACM, 2010,
pp. 523–534.
[4] Dean, J. and Ghemawat, S.: MapReduce: a flexible data processing tool, Communications of theACM, Vol. 53, No. 1(2010), pp. 72–77.
[5] Harris, T., Marlow, S., Peyton-Jones, S., and Herlihy, M.: Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposiumon Principles and practice of parallel programming,ACM, 2005, pp. 48–60.
[6] He, B., Fang, W., Luo, Q., Govindaraju, N. K.,

and Wang, T.: Mars: a MapReduce framework ongraphics processors, Proceedings of the 17th international conference on Parallel architectures andcompilation techniques, ACM, 2008, pp. 260–269.
[7] Ranger, C., Raghuraman, R., Penmetsa, A.,
Bradski, G., and Kozyrakis, C.: Evaluating mapreduce for multi-core and multiprocessor systems,
IEEE 13th International Symposium on High Performance Computer Architecture, IEEE, 2007,
pp. 13–24.
[8] Sutter, H.: The free lunch is over: A fundamental
turn toward concurrency in software, Dr. Dobb sJournal, Vol. 30, No. 3(2005), pp. 202–210.
[9] Talbot, J., Yoo, R. M., and Kozyrakis, C.:
Phoenix++: modular MapReduce for sharedmemory systems, Proceedings of the second international workshop on MapReduce and its applications, MapReduce ’11, New York, NY, USA, ACM,
2011, pp. 9–16.