Xiongli Gu
email: guxiongli2010@gmail.com

Jie Yang

Xiamin Wu

Chunming Huang

Peng Liu
email: liupeng@zju.edu.cn

An Efficient Architectural Design of Hardware Interface for Heterogeneous Multi-core System

Keywords: data flow graph (DFG), multi-core system, parallel programming

How to manage the message passing among inter processor cores with lower overhead is a great challenge when the multi-core system is the contemporary solution to satisfy high performance and low energy demands in general and embedded computing domains. Generally speaking, the networks-on-chip connects the distributed multi-core system.

It takes charge of message passing which including data and synchronization message among cores. The size of most data transmission is typically large enough that it remains strongly bandwidth-bound. The synchronization message is very small which is primarily latency bound.

Thus the separated networks-on-chip are needed to transmit the above two types of message. In this paper we focus on the network for the transmission of synchronization messages. A hardware modulemessage passing unit (MPU) is proposed to manage the synchronization message passing for the heterogeneous multi-core system. Compared with the original single network approach, this solution reduces the run-time object scheduling and synchronization overhead effectively, thereby, improving the whole system performance.

Introduction

Nowadays multi-core system becomes a popular solution for obtaining higher performance, short developing period, and low cost in the application system design.

The multi-core system has its advantages but it also brings new problems: the run-time concurrency and synchronization among tasks are crucial if the high system performance is pursued [START_REF] Mignolet | MPA: parallelizing an application onto a multicore platform made easy[END_REF].

We use the data flow graph (DFG) programming model to guide the parallel programming [START_REF] Robert | Ⅱ: Parallel processing with large grain data flow techniques[END_REF] in our work. The compiled inter-processor tasks are statically mapped to the distributed processors and the synchronization message passing among inter processors are needed for the parallel running of tasks on different processors.

Usually the size of synchronization message is small which should be transmitted among processors with lower latency. But the traditional networks-on-chip is usually designed for the data transmission and is not efficient to manage the synchronization message passing among inter cores.

In this paper we suggest a hardware module called message passing unit (MPU) which transmits the scheduling and synchronization message for the lightweight distributed multi-core system without shared memory. The aim of this work is to reduce the inter processor communication overhead. We consider that NoC should not only play the role of data transmission but also help to manage part of the application scheduling and synchronization work for the multi-core system. The constructs in the application program for handling coordination and synchronization between the threads are transferred to the control signals that shall be sent and/or received by the processors during runtime. The control signals are short and they should be transmitted fast with less overhead. If they are transmitted in the same network as data the average overhead is expensive which is usually unacceptable. So in the NoC design space we specify two sub layers in the link/network layer: the data transmission sub layer manages the data communication. The control sub layer -MPU manages the control signal flow and messages passing for handling the coordination and synchronization among threads which is efficient for the heterogeneous multi-core system.

The rest of the paper is organized as follows: Section 2 gives an overview of related work. Section 3 explains our MPU proposal. Section 4 describes the implementation details of object scheduling and synchronization flow. Section 5 discusses the evaluation methodology and gives the evaluated results. Finally conclusions are made.

Related work

In the literature, there are some prior work have been done to accelerate the synchronization message passing among inter cores. In [START_REF] Paulin | Parallel programming models for a multiprocessor SoC platform applied to networking and multimedia[END_REF], the MultiFlex uses the object request broker (ORB) to connect client task to the server task. The aim is to accelerate the scheduling and synchronization message passing among tasks. In [START_REF] Abdelrahman | The MLCA: a solution paradigm for parallel programmable SoCs[END_REF], the MLCA adopts universal register file (URF) to exchange the scheduling and synchronization message passing among inter-core tasks. But the ORB and URF have the same problem: they transmit the scheduling and synchronization message in the general NoC. The general NoC is designed for data transmission among inter cores, which usually has large bit-width and the complicated protocol to assure the correct data transmission. As a result, the complicated protocol will bring overheads. Thus the traditional NoC is not efficient to manage the small size synchronization message passing among inter-core tasks. In [START_REF] Cheng | An object oriented model scheduling for Media-SoC[END_REF], DMA based message passing mechanism is applied in Cheng's work to transmit the synchronization messages among inter-core tasks which is also inefficient for the transmission of synchronization message.

Construct of MPU 3.1 Application model

Before describing the proposed MPU, the application model is firstly introduced. The tasks of a data-driven workload can be modeled as a data flow graph. Definition 1: A data flow graph (DFG) [START_REF] Sinnen | Task scheduling for parallel systems[END_REF] is a directed graph DFG(V, E, D), where each node n i  V represents a task and a directed edge e k =(n i , n j )E represents the communication between nodes n i and n j. . The tasks are mapped onto processors statically at compile time. All tasks are executed in a self-timed manner [START_REF] Bekooij | Dataflow analysis for real-time embedded multiprocessor system design[END_REF] as follows: a task can be invoked if (1) it receives the data from all its predecessors and (2) its output data buffers are valid. The above two operations are based on message passing mechanism. So the MPU should manage the message passing for these two operations of message passing architecture. The tasks are executed atomically and in this paper we define the atomic task as object.

MPU structure

A hardware/software implementation for the object scheduling, synchronization and data transmission between objects is proposed. Essentially the function of real-time operating system (RTOS) task/thread management is partly realized in hardware, which is named message passing unit (MPU) and situated in the link/network layer of NoC. As described in Section 1, MPU is also the control sub net of NoC, which takes advantage of the multi-core system's characteristics and transmits the control signals and messages for object scheduling and synchronization efficiently.

The task/thread management is the controller of the scheduler. The producer processor informs MPU that its object execution has been completed and then MPU wakes up the consumer objects to start processing the incoming data. This message passing mechanism realized in the control sub net guides the scheduling and synchronization of the different objects. The DMA tasks are also set by MPU to transfer the data between the producer and consumer objects.

MPU hardware architecture

The hardware module of MPU supports four functions, (1)receive and response to the producer object information, (2)wake up the available consumer objects for execution, (1) The object scoreboard records the status of objects which are running or pending in the multi-core system. It is the kernel part for message interchange. Each processor in the multi-core system has one corresponding entry (in Fig. 1 it is supposed that the system has four processors) in the object scoreboard, which records the status of the objects assigned to this processor. The length of entry is decided by the maximum number of objects that can be mapped to the processor. Each processor or object can write data in one bank of register cluster, and each processor (or object) can read every entry of the register cluster. So the message passing among tasks are realized in this way. Each entry includes five fields: counter, data_ready, syn_consumer_read, syn_consumer_processed, and process_enable.

i) Counter field

The counter field records the input data port number of the objects allocated on this processor.

ii) Data_ready field

This field is set by the related producer objects allocated in the other processors, which is used to inform the consumer objects that the input data has been ready.

iii) Syn_consumer_read field

The syn_consumer_read field is designed to realize the synchronization for data reading.

iv) Syn_consumer_processed field

This field is served as the synchronization point to assure the synergistic working of the producer and consumer objects pair in the multi-core system.

v) Process_enable field

In our execution model the object should be executed atomically. When one object is in its execution, the other objects cannot interrupt it. This is realized by tag set in the process_enable field.

(2) The wakeup logic selects the available objects for execution.

(3) The object program counter array records the starting addresses of objects.

(4) The DMA task parameter buffer is used to store the DMA operation parameters which the global memory address, the local memory address, the data length and the data format are set in its entries. Directors call for the DMA operation when the input data is ready.

Operating system interface for MPU

We design four functions in RTOS for MPU to manage the task/thread running of multi-core system. These functions include Write_MPU(), Syn_consumer_read(), Syn_consumer_processed(), and Check_MPU().

(1) The Write_MPU function is used by the director of producer object to set and clear its consumer object's data ready fields in the entry of object scoreboard.

(2)The Syn_consumer_read function is called by the director of consumer object to set its syn_consumer_read field of the object scoreboard.

(3)The Syn_consumer_processed function is used by the director of consumer object to clear its syn_consumer_processed field.

(4)The Check_MPU function is applied to check the object status in an entry of object scoreboard.

These four functions constitute main part of the task/thread management of RTOS, which handles the objects operation in the multi-core system.

Object scheduling and synchronization flow

The scheduling and synergistic synchronization management for the running of the parallel program are partly performed by the hardware MPU and partly by softwarethe director in RTOS. The hardware MPU manages the object waken-up and part of the operation of synergistic synchronization for the objects execution in the multi-core system. After the object scoreboard entries have been set by the producer object which completed its execution, the DMA operation will be called first to transfer the produced output data to the local memories of the consumer objects. Then the consumer objects which have all the input data ready can be selected for execution by the wakeup logic. The whole flow includes the following steps.

(1) The syn_consumer_processed bit becomes unavailable after the data ready bit has been set. The MPU sends the DMA operation interruption signal to the corresponding consumer object director to initiate the data transfer between the producer and consumer objects. When the DMA operation is over, the director of consumer object will set syn_consumer_read bit and decrease the number by one in the corresponding counter. Later the data ready bit will be cleared by the producer object.

(2) The wakeup logic scans the counters to find out the ready objects for execution. If the processor of the ready object is free (process_enable bit is available) the highest priority ready object will be activated, MPU sends execution interruption signal to the corresponding processor. Then this processor fetches the program from the address indicated by the PC array.

(3) After the scheduled object finishes its execution the result data will be written to the global memory and its consumer objects' entries in the object score board will be set if they have completely processed the former produced data (all the syn_consumer_processed bits of its consumer objects are cleared). Then this producer object's syn_consumer_processed bit is cleared, process_enable is reset to valid and the counter is reset to its input data number by hardware.

Thus it means that the parallel program has finished its execution for one batch of its input data, the process mentioned above will be repeated cyclically for the successive batches of the input data. The MPU scheduling flow is depicted in Fig. 2.

Experimental results

Evaluation methodology

In order to evaluate the proposed MPU performance two applications -FFT program [START_REF] Cooley | An algorithm for the machine calculation of complex Fourier series[END_REF] and eigenvalue of matrix -Jacobi algorithm [START_REF] Golub | Eigenvalue computation in the 20th century[END_REF] program are adopted in the experiment. The experimental platform integrates one 32-bit integer RISC core -RISC32E [START_REF] Xiao | Optimizing pipeline for a RISC processor with multimedia extension[END_REF] and eight 32-bit integer DSPs -MediaDSP3200 [START_REF] Liu | 32-bit media digital signal processor[END_REF][START_REF] Shi | 32b RISC/DSP media processor: MediaDSP3201[END_REF]. A 3x3 mesh topology NoC connects them and the DMA engine is also included. Each core has a local memory and the SDRAM is used as the global data buffer for the application.

Each DSP has one allocated director and RTOS is running on the RISC processor. The MPU and software directors (proxy of RTOS) manage the object scheduling and synchronization for this multi-core system.

The fast Fourier transform (FFT)

The fast Fourier transform (FFT) is the fast algorithm for DFT and one of the most popular algorithm is the Cooley-Turkey algorithm which is written as below:

2 1 2 2 2 1 1 1 2 1 2 1 1 1 1 2 1 2 0 0 [ , ] [ , ] N N n k n k n k N N N n n X k k W W x n n W              -point DFT transfer 2 1 [ , ] x n k 2 2 2 2 2 1 2 1 0 [ , ] N n k N n W x n k     1 N -point DFT transfer 2 N , 11 2 1 2 22 01 01 nN n N n n nN           , 11 1 1 2 22 01 01 kN k k N k kN           , 12 N N N  .
In the experiment 64-point FFT is applied as the test algorithm. The 64-point FFT on platform is arranged as N 1 =N 2 =8 and Fig. 3 shows its parallel programming process and synchronizations among objects. 1) The object t 00 is the predecessor for the inter-processor objects t 1j (j=1…8), which calculates the indexes for original data. It is allocated to the control RISC.

2) The objects t 1j (j=1…8) calculate the inner summation algorithm of the

FFT 1 1 1 1 1 2 1 1 0 ] , [ k n N N n W n n x   
by using the FFT algorithm. The objects are allocated to DSPs.

3) The object t 20 calculates the The experimental results are shown in Table 3. From Table 3 we can see that the MPU solution has less memory space requirement for RTOS kernel and directors. It takes an average time consumption of 16018 cycles for one time 64-point FFT. The kernel delay for the scheduling and synchronization of MPU approach takes up 8.96%

and for software director the percentage is 31.53%. Thus the MPU efficiently reduces the kernel delay for the multi-core system which improves the system efficiency by 24.79%.

Eigenvalue of matrix

The eigenvalue λ of matrix A is defined as Au = λu, where A is an n x n matrix, λ is a real number and u is the n dimensional characteristic vector of matrix A. The Jacobi matrix algorithm is applied to solve this problem. In experiment a 64*64 matrix is applied as the test algorithm. The Fig. 4 shows its parallel programming process and the synchronizations among objects.

1) The object t 00 assigns the matrix coefficients of A to the DSPs, which is the predecessor of objects t 1j (j=1…8). It is allocated to control RISC.

2) The objects t 1j (j=1…8) divide the assigned coefficients into upper diagonal and lower diagonal classes. They are the predecessors of object t 20 which are allocated to DSPs.

3) The thread t 20 finds the maximum value from the collected biggest values, which is the predecessor of objects t 60 and t 3j . It is allocated to control RISC.

4) The objects t 3j (j=1…8) calculate the tangent of rotating angle θ of hyper plane (g, h), cos θ and sin θ, which are the predecessors of objects t 5j (j=1…8) and are allocated to DSPs.

5) The object t 40 broadcasts the matrix coefficients of row g and column h to the DSPs, which is the predecessor of objects t 5j (j=1…8). It is allocated to control RISC.

6) The objects t 5j (j=1…8) performs multiplication of the former result (P gh

P gh (2) …P gh (k-2) ) by P gh (k-1) , which are the predecessors of t 1j and are allocated to DSPs.

7) The object t 60 get the final results, which is allocated to control RISC. The eigenvalue of matrix's result is shown in Table 4. Similarly, the memory space requirement of MPU is less than the software director's. The one-time 64*64

Jacobi matrix algorithm calculation needs 48945 cycles so that the kernel delay of MPU approach takes up about 11.51% of the whole time consumption and for software director the percentage is 26.82%. Thus the MPU scheme reduces the kernel delay which improves the system efficiency by 17.30%.

Physical parameters of MPU

The hardware cost of MPU depends on the scale of multi-core system and the maximum number of threads/objects which are allocated on the processors. Here the scale of MPU is for nine processors multi-core system so that there are nine entries in the object scoreboard. For a limited number of threads exploited in the program it is supposed that each processor has no more than four threads/objects. In the multi-core system each object may have maximum eight producers and eight consumers so every object needs 27-bit for the entry. At the same time a 32-bit program counter and a 128-bit DMA task parameter buffer are needed for one object. So a 187-bit width hardware register is needed for one object in total. The 3x3 mesh topology NoC is used which the channel width is 64-bit and the depth of the FIFO is 8. We synthesize the MPU module and NoC module using Synopsys v-2003.6 and the TMSC90 CMOS process technology. The physical parameters of MPU and NoC are listed in Table 5.

From Table 5 we can see that the MPU module can work at the NoC frequency and the area cost of MPU takes up 14.5% of the whole NoC area.

Conclusion

The hardware/software approachmessage passing unit interface offers an efficient way to manage the object scheduling and synchronization for the multi-core system to reduce the communication overhead. Compared with the software director, it not only cut down the average delay for object scheduling and synchronization but also reduces the code size for RTOS and director, which is usually important for the limited memory space of the embedded system. The physical parameters imply that the hardware MPU module has the characteristic of relatively higher frequency and small area. Compared with the software approach the MPU approach improves the system efficiency by 24.79% in FFT application and 17.30% in Jacobi matrix algorithm with the hardware area increase of 14.5%.

( 3 )Fig. 1 .

 31 Fig.1. Block diagram of MPU hardware

Fig. 2 .

 2 Fig.2. MPU scheduling and synchronization flow

Fig. 3

 3 Fig. 3 Parallel programming process and synchronizations in FFT

W 5 )

 5 which multiplies by input data and finishes the data permutation operation from the order ofx[k 1 ,n 2 ] to x[n 2 ,k 2 ]. It is allocated to the control RISC.4) The objects t 3j (j=1…8) calculate the summation algorithm of the FFT algorithm. The objects are allocated to DSPs. The object t 40 manages the output data permutation to the frequency domain parameter and is allocated in control RISC.

Fig. 4

 4 Fig.[START_REF] Abdelrahman | The MLCA: a solution paradigm for parallel programmable SoCs[END_REF] Parallel programming process and synchronizations in Jacobi matrix algorithm

Table 3 .

 3 FFT experimental result

	Scheduler	Overhead	RTOS kernel on RISC(Kbytes)	Director on processor(Kbytes)	Kernel delay/ total execution time (cycles)
	Software Director	10	1.884	6716/21299
	MPU	9	0.584	1435/16018

Table 4 .

 4 Jacobi matrix algorithm experimental result

	Scheduler	Overhead	RTOS kernel on RISC(Kbytes)	Director on processor(Kbytes)	Kernel delay/ total execution time (cycles)
	Software Director	10.298	2.182	15870/59182
	MPU	9.494	0.974	5633/48945

Table 5 .

 5 Physical parameters of MPU and NoC (TSMC90: worst case, voltage 1.08v,

	temperature 125℃)
	Parameter Component	Delay (ns)	Frequency (MHz)	Gate count	Dynamic power (mW)
	MPU	0.85	1176	97096	6.42
	NoC	1.30	769	669634	80.82

The corresponding author, liupeng@zju.edu.cn

Acknowledgment

This work is supported by NSFC under grant 60873112.


Jie Tang

Shaoshan Liu

Zhimin Gu
email: zmgu@x263.net

Chen Liu
email: chen.liu@fiu.edu

Jean-Luc Gaudiot
email: gaudiot@uci.edu

Memory-Side Acceleration for XML Parsing

As Extensible Markup Language (XML) becomes prevalent in cloud computing environments, it also introduces significant performance overheads. In this paper, we analyze the performance of XML parsing, identify that a significant fraction of the performance overhead is indeed incurred by memory data loading. To address this problem, we propose implementing memory-side acceleration on top of computation-side acceleration of XML parsing. To this end, we study the impact of memory-side acceleration on performance, and evaluate its implementation feasibility including bus bandwidth utilization, hardware cost, and energy consumption. Our results show that this technique is able to improve performance by up to 20% as well as produce up to 12.77% of energy saving when implemented in 32 nm technology.

Introduction

One of the main challenges in cloud computing environments is data exchange between different platforms. XML is emphasized for its language neutrality and application independency, and thus it has been adopted as the data exchange standard in cloud computing environments. When data is in XML, thousands of existing software packages can handle that data. Data in XML is universally approachable, accessible, and usable. Although XML exhibits many benefits, due to its verbosity and descriptive nature, XML parsing has incurred heavy performance penalties [START_REF] Chiu | Investigating the limits of soap performance for scientific computing[END_REF][START_REF] Head | Grid scheduling and protocolsbenchmarking XML processors for applications in grid Web services[END_REF].

Studies have shown that servers spend a significant portion of their execution time on processing XML documents. A real world example would be Morgan Stanley's Financial Services system, which spends 40% of its execution time on processing XML documents [START_REF] Apparao | Architectural characterization of an XML-centric commercial server workload[END_REF]. This is only going to get worse as XML data get larger and more complicated. Generally, in cloud computing environments, XML parsing is memory and computation intensive, it consumes about 30% of processing time in web service applications [START_REF] Apparao | A detailed look at the characteristics of XML parsing[END_REF], and has become a main performance bottleneck in real-world database servers [START_REF] Nicola | XML parsing: A threat to database performance[END_REF].

To improve performance of XML processing, many have proposed computationside acceleration techniques. In this paper, we find out that memory accesses actually incur significant performance overheads in XML parsing. Therefore, different from previous studies which focus on computation acceleration, we propose to accelerate XML parsing from memory side. Unlike computation acceleration, which has a strong dependency on the parsing model, memory-side acceleration is generic and can be effective across all parsing models. We believe the combination of computation-side and memory-side acceleration will largely relieve the performance pressure incurred by XML parsing. In our vision, cloud computing services can be hosted by one many-core chip, such as Intel's SCC chip [START_REF]Intel Single-Chip Cloud Computer[END_REF]. Within this many-core chip, we should have at least one core act as the Data Exchange Frontend (DEF), which is dedicated to and optimized for XML parsing; and this DEF core should incorporate special instructions for computation-side acceleration as well as dedicated prefetchers for memory-side acceleration.

Within this context, we aim to answer three questions in this paper: first, what is the performance bottleneck of XML parsing? Second, can memory-side prefetching techniques improve the performance of XML parsing? Third, is it feasible to implement these techniques in hardware? The rest of this paper is organized as follows: in section 2, we review XML parsing techniques and related research work; in section 3, we discuss the methodology of our study; in section 4, we study the performance of XML parsing under native and managed environments; in section 5, we aim to answer the first question by evaluating the performance of XML parsing and identify the performance bottleneck of XML parsing; in section 6, we aim to answer the second question by delving into memory-side acceleration of XML parsing ; In section 7, we aim to answer the third question by studying the implementation feasibility of the memory-side acceleration. At the end, we conclude and discuss our future work.

Background

In this section, we review XML parsing techniques as well as related studies on software and hardware acceleration of XML parsing.

XML Parsing Techniques

Based on how data is processed, there are two categories of XML parsing models: event-driven parser and tree-based parser. Event-driven parsers first parse the document, and then through callbacks, they notify client applications about any tag they find along the way. It transmits and parses XML infosets sequentially at runtime. As a result, Event-driven parsers don't cache any information and have an enviably small memory footprint. However, it does not expose the structure of the XML documents, making them hard to manipulate. Furthermore, according to how events are delivered, event-driven model can be divided into two classes: pull parser and push parser. In pull parsing, clients pull XML data when it is needed. In push parsing, an XML parser pushes XML data to the client as new elements are encountered. Simple API for XML (SAX) [START_REF]SAX Parsing[END_REF] is the industry standard for push based event-driven model. As shown in upper part of Figure 1, SAX processes the XML document and then pushes the XML information into Application in terms of SAX Events.

On the other hand, tree-based parsers read the entire content of an XML document into memory and create an in-memory tree object to represents it. Once in memory, DOM trees can be navigated freely and parsed arbitrarily for the duration of the document processing, providing maximum flexibility for users. However this flexibility pays great costs of a potentially large memory footprint and significant processor requirements. Document Object Model (DOM) [START_REF]W3C, -Document object model (DOM) level 2 core specification[END_REF] is the official W3C standard for tree-based parser. As shown in bottom part of Figure 1, DOM parser processes XML data, creates an object-oriented hierarchical representation of the document and offer the full access to the XML data.

Related Research Work

There have been several proposals on mitigating the performance overheads of XML processing. In software community, several researcher groups employed the concept of binary XML to avoid performance bottleneck of XML parsing [START_REF] Chiu | Investigating the limits of soap performance for scientific computing[END_REF][START_REF] Chiu | A binary XML for scientific applications[END_REF][START_REF] Ximpleware | VTD-XML: The Future of XML Processing[END_REF]. Specifically, VTD-XML parser [START_REF] Ximpleware | VTD-XML: The Future of XML Processing[END_REF] parses XML documents and creates 64-bit binary format VTD records. However, the major shortcoming of this approach is that the parsed binary data can't be used by other XML applications directly. On the other hand, some researchers focus on parallelizing the parsing process. Pre-scanning based parallel parsing model [START_REF] Lu | A Parallel Approach to XML Parsing[END_REF] builds a skeleton of the XML document to guide partitioning of the document for data parallel processing. Also, in [START_REF] Michael | Approaching a Parallelized XML Parser Optimized for Multi-Core Processor‖[END_REF] researchers exploited the parallelism by dividing XML parsing process into several phases, so that they can schedule working threads to execute each parsing phase in a pipeline model. In addition, Parabix employs the SIMD capabilities of commodity processors to process multiple characters at the same time [START_REF] Cameron | High Performance XML Parsing Using Parallel Bit Stream Technology[END_REF].

In the hardware community, based on the profiling analysis, researchers incorporate new instructions with special hardware support to speedup certain frequently-used operations of XML parsing [START_REF] Zhao | Performance Evaluation and Acceleration for XML Data Parsing[END_REF]. In [START_REF] Moscola | Reconfigurable Content-based Router using Hardware-Accelerated Language Parser[END_REF], researchers presented a technique to automatically map regular expressions directly onto FPGA hardware and implemented a simple XML parser for demonstration. Their technique could be not sufficient to solve all problems since XML syntax rule is not a regular language. XOE [START_REF] Nag | Acceleration techniques for XML processors[END_REF] use an Offload Engine to accelerate XML document parsing. Some fundamental parsing functionality like tokening is offloaded to XOE. XPA [START_REF] Dai | A 1 Cycle-Per-Byte XML Parsing Accelerator[END_REF] is another XML Parsing Accelerator implemented on FPGA capable to do XML well-formed checking, schema validation, and tree construction. It can reach up to1 Cycle-Per-Byte throughput for XML parsing. Nevertheless, their design works only for treebased parsers. As we show in the following sections, memory access is one of the major bottlenecks of XML parsing, thus we may be able to generate extra performance gain from memory-side acceleration. In addition, unlike computationside acceleration that targets specific parsing model, memory-side acceleration is generic and can be effective regardless of the parsing model.

Methodology

In this section, we discuss our methodology to study the performance of XML parsing, the effectiveness of memory-side acceleration, and implementation feasibility.

XML Parsers and Benchmarks

In order to make fair comparison, we choose XML parser implementations of both event-driven and tree-based model from Apache Xerces [18]. Apache Xerces provides SAX and DOM XML parsers, and it has implementations of these two models in both native (C++) and managed (Java) environments. This allows us to perform a thorough study to understand the performance of SAX and DOM models in different execution environments. As for inputs to the XML parsers, we have selected seven real world XML documents with varying sizes (from 1.4 KB to 113 MB) and complexities as input data and they are listed in Table 1. Specifically, personalschema is a very simple document with flat structure, thus the parsing process is straightforward; on the other hand, standard is a long document with deep structures, which complicates the parsing process.

Prefetchers

In this study, we evaluate how different prefetching techniques impact the performance of XML parsing. In order to make a comprehensive investigation, we have selected eight hardware prefetchers, which utilize different techniques and algorithms. We summarize these prefetchers in Table 2: cache hierarchy indicates the coverage of the prefetching, which means if the prefetching is applied at L1 cache, L2, cache, or both; prefetching degree suggests whether the aggressiveness of the prefetcher is statically or dynamically adjusted. Usually, the dynamic prefetching degree can adapt itself to the phase change of the application so as to produce more efficient prefetching; trigger L1 and trigger L2 respectively show the trigger set for covered cache hierarchy respectively, in this case demand access stands for access requests from upper memory hierarchy regardless whether it is a miss or hit and N/A means no prefetching is applied. Since demand access trigger set contains more opportunity to invoke the prefetching, it always yields more aggressiveness. Besides, all selected prefetchers can filter out redundant access requests. The aggressiveness of the prefetching is the co-production of all these four metrics and prefetching algorithms. The first prefetcher n1 can tolerate out of order memory accesses by making prefetching based on the recent memory access pattern. The second prefetcher n2 exploits various localities in both local and global cache-miss streams, including global strides, local strides and scalar patterns. A multi-level prefetching framework is applied in n3: it uses a sequential tagged prefetcher at L1 cache and either an adaptive prefetcher or a sequential tagged prefetcher at L2 cache. With the observation that memory accesses often exhibit repetitive layouts spanning large memory region, n4 is the optimized implementation of Spatial Memory Streaming (SMS) including a novel mechanism of pattern bit-vector rotation to reduce SMS storage requirement. Combining the storage efficiency of Reference Prediction Tables and high performance of Program Counter/Delta Correlation (PC/DC) prefetching, n5 can substantially reduce the complexity of PC/DC prefetching by avoiding expensive pointer chasing and re-computation of the delta buffer. The sixth prefetcher n6 applies a hybrid stride/sequential prefetching schema at both L1 and L2 cache levels. Metrics such as prefetcher accuracy, lateness and memory bandwidth contention are fed back to adapt the aggressiveness of prefetching. By understanding and exploiting a variety of memory access patterns, n7 combines global history buffer and multiple local history buffers to improve the coverage of prefetching. Finally, n8 is a stream-based prefetcher with several enhancement techniques including constant stride optimization, noise removal, early launch of repeat stream and dead stream removal.

Performance and Memory Modeling

To study the performance of the memory-side acceleration, we utilize CMP$IM [START_REF] Jaleel | CMP$im: A Pin-Based On-The-Fly Multi-Core Cache Simulator[END_REF], a binary-instrumentation based cache simulator developed by Intel. CMP$IM is able to characterize cache performance of single-threaded, multi-threaded, and multiprogrammed workloads. The simulation framework models an out-of-order processor with the basic parameters as outlined in Table 3. To understand the implementation feasibility of these memory-side accelerators, we also study the energy consumption of these designs. To model the energy consumption of these prefetchers, we utilize CACTI [START_REF] Shivakumar | CACTI3.0: an integrated cache timing, power, and area model[END_REF], an energy model which integrates cache and memory access time, area, leakage, and dynamic power. Using CACTI, we are able to generate energy parameters of different storage and interconnect structures implemented in different technologies. Note that the overall system energy consumption consists of two sources: static power and dynamic power. Static power is generated by the leakage current of the transistors, and it persists regardless of whether the transistors are actively switching or not. On the other hand, dynamic power is incurred only when the transistors are actively switching. In this paper, we use CACTI to model both static and dynamic energy to evaluate the implementation feasibility of memory-side accelerators.

Native vs. Managed Execution

In this section, we study the performance of XML parsing in both managed and native environments. We executed XML parsers on a dual-core machine running at 2.2 GHz and used the Intel Vtune analysis tool [START_REF]Intel Vtune[END_REF] to capture the overall execution time. The results are shown in Figure 2, in which we take the performance of native execution as the baseline. The x-axis shows the seven benchmarks and the y-axis shows the percentage of the excess execution time incurred by the managed layer (in this case JVM). It is obvious that when parsing with SAX model, managed execution produces high performance overhead. For instance, when parsing test-opc and mystic-library, the managed middle layer contributes 41.67% and 38% performance overhead respectively. Even in the best case, long, the middle layer still incurs 20.73% performance overheads. The situation is even worse when using DOM parsing model. Even the best case has incurred 25.93% performance overheads. In the worst case, test-op, it incurs up to 52.08% performance degradation. Although managed environment is able to reduce development time, in cloud computing environments, XML parsers reside at the data exchange frontend and many other components in the system may have dependency on the outputs of the XML parsers. Therefore, the performance overheads incurred by the managed layer would largely hinder the performance of the whole system. This result indicates that managed execution of XML parsing is not suitable in cloud computing environments and we focus on native execution of XML parsing in the rest of this paper.

Performance Analysis of XML Parsing

In this section we aim to determine the performance bottleneck of XML parsing by studying the throughput of XML parsing at different parts of the system, including network data exchange, disk I/O, and memory accesses. Figure 3 shows the data flow of XML parsing: first, data is loaded from either network or local hard disk. Then, data flows into the memory subsystem: main memory, L2 and L1 caches. At the end, the processor fetches data from cache and performs the actual XML parsing computation.

Hard Disk

Network

Memory

Subsystem Processor

Disk I/O Network Data Access Memory Access

Figure 3:Data flow of XML data parsing

Network Data Exchange

Some previous work has demonstrated that network data exchange would incur significant performance overheads [START_REF] Lee | Accelerated Network Coding with Dynamic Stream Decomposition on Graphics Processing Unit‖[END_REF][START_REF] Park | On Improving Parallelized Network Coding with Dynamic Partitioning‖[END_REF]. In this subsection, we measure the data exchange throughput of different cloud data services. In

Disk data loading

In order to study the disk I/O throughput, we used the XPerf Performance Analyzer tool [START_REF]Windows Performance Analysis Tool[END_REF] to capture disk I/O throughput when running the XML parsers using the standard benchmark, and the collected results are shown in Figure 4: the x-axis shows the execution timeline in seconds and the y-axis shows the amount of triggered disk I/O during the execution. The gray curve overlaid on top of the bar diagram shows the CPU usage information. The peak of the curve means the CPU is fully utilized. Figure 4 shows that most of the time disk I/O is in the underutilized state; that is to say that the I/O subsystem rarely needs to reach its full capacity. Besides, when looking into the overlaid CPU usage curve, it shows that most of the time the CPU is fully utilized, running at 100%. Once in a while, the CPU utilization drops down, probably due to high-latency memory accesses. It indicates that in this case most of the time CPU is fed with enough data from the I/O subsystem. Based on these observations, it can be concluded that disk I/O is also not likely to be the bottleneck of XML data processing. We also ran the XML parsers with other benchmarks shown in Table , and the results were similar.

5.3

Data loading from memory side Finally, we studied the overhead produced by memory data loading stage. Here, memory data loading refers to the data flow starting from main memory, going through each cache layer and finally fetched into CPU. Making a comparison, we measured the CPI (cycle per instruction) of Speed-test, which is a computation intensive CPU stress test application with negligible memory access; and we measured the CPI of native XML parser using the standard benchmark, which is the large XML document with a lot of memory accesses. The CPI of Speed-test is 0.80. Using the SAX parser, the CPI of standard is 1.27, which introduces nearly 50% overheads compared to Speed-test; using the DOM parser, the CPI of Standard becomes 1.42, which nearly doubles that of Speed-test. In addition, when using other benchmarks shown in Table 1, we obtained similar performance data as that of standard.

As a further validation, we measured the miss count per kilo instructions (MPKI) of both L1 and L2 cache layers, which are nearly 10 and 2 respectively. That is to say that for every 1000 instructions there comes about ten L1 and two L2 cache misses. The large number of cache misses mainly contributes to the CPI increase of XML parsing. Compared with the CPI of Speed-test, the extra cycles consumed by XML parsing may indicate that memory data loading stage incurs a significant amount of overhead to the execution.

5.4

Summary In summary, the results from the previous three subsections show the following: first, network I/O throughput can easily reach over 15 MB/s, and this is far below the 100 MB/s network bandwidth limit, showing that network I/O is far from being stressed and network data exchanging is not likely to be the bottleneck of XML parsing. Second, our experiment results show that the disk I/O subsystem is under-utilized most of the time, which means disk data loading of XML data parsing is within the coverage of disk I/O subsystem and cannot be the bottleneck of execution as well. At last, comparing CPI data of XML parsing workloads and a CPU stress test, we have found that in some case the CPI of XML parsing almost double that of the CPU stress test. Upon further analysis, we have found that the high cache miss rate on both L1 and L2 caches is the main contributor to this CPI increase. These results indicate that the performance bottleneck of XML parsing is memory data loading stage; in other word, the overheads introduced from memory subsystem really hit the pain point of XML data parsing. Therefore, in order to speed up the XML parsing execution, it is imperative to turn around the focus of acceleration and reduce the overheads incurred by the memory subsystem.

Memory-Side Acceleration

We have identified that memory accesses impose significant overheads in XML parsing workloads. Similarly, a study released by Intel verifies that memory accesses contribute to more than 60% execution cycles of the whole parsing process [START_REF]XML Parsing Accelerator with Intel® Streaming SIMD Extensions 4 (Intel® SSE4)[END_REF]. Furthermore, another empirical study done by Longshaw et al. has shown that loading an XML document into memory and reading it prior to parsing may take longer than the actual parsing time [24]. Consequently, instead of optimizing specific computation of parsing model, we explore acceleration from memory side; that is to say, accelerate the XML data loading stage.

Table 5 summarizes the reduction of cache misses as a result of applying the prefetchers (please refer to section 3.2 for the details of the prefetchers). Note that different prefetchers may target different cache levels; in this table, we show the cache miss reduction of the lowest level cache that the prefetcher is applied to. For example, n1 is applied to both L1 and L2 caches, we show the cache miss reduction of L2 cache; n2 is applied to only L1, so we show the cache miss reduction of L1 cache. The results indicate that prefetching techniques are very effective on XML parsing workloads, as most prefetchers are able to reduce cache miss by more than 50%. In the best case, n3 is able to reduce L2 cache miss by 82% in SAX and 85% in DOM.

In Figure 5, we show how the cache miss reduction translates into performance improvement on SAX parsing: it shows the performance of the eight prefetchers (n1-n8) as well as the average performance. The X-axis lists the seven benchmarks we used and the Y-axis shows the percentage of performance improvement (in terms of execution time reduction). The results indicate that prefetching techniques are able to improve SAX parsing performance by up to 10%. For instance, on average, the parsing time of personal-schema has been reduced by 7.24%. Even in the worst case, standard, prefetchers are still able to reduce execution time by 3%. Looking into each prefetching technique, we observe that n3 shows greatest power in improving the performance by 2.58% to 9.72% across different benchmarks. This is because n3 is the most aggressive prefetcher and covers both L1 and L2 cache level, thus resulting in the best average performance.

Similarly, Figure 6 summarizes the performance impact of prefetching on DOM parsing. The results indicate that prefetching techniques are able to improve DOM parsing performance by up to 20%. For instance, when averaging the results, memory-side acceleration produces 13.74% execution cycle reduction for mysticlibrary. It is obvious that the most effective prefetcher is still n3:even in the worst case, n3 can still reduce execution time by 6%. Note that different from SAX parsing, DOM must construct inner data structure in memory for all elements. The bigger the document is the more space it would consume, and the more cache miss it would induce. As a result, large sized benchmarks such as mystic-library, physics-engine and standard can get a higher performance gain from memory side acceleration from 7.65% up to 13.75%. These results confirm that memory-side acceleration can be effective regardless of the parsing models.

Implementation Feasibility

By now we have shown that memory-side acceleration can significantly improve XML parsing performance. However, the conventional wisdom is that prefetching requires extra hardware resource, competes for limited bus bandwidth, and consumes more energy. Thus, many would argue that it is not worthwhile to implement memory-side accelerators for XML parsing. In this section, we address these doubts If the application itself has used up all the bus bandwidth, then the contention brought in by memory-side acceleration might hinder rather than improve performance. Hence, we study the bandwidth utilization of XML parsing workloads and the results are summarized in Table 6. The results show that bus bandwidth utilization without prefetching is far away from exhaustion. On average, bus utilization for SAX and DOM parsing are only 3.72% and 5.51% respectively. This indicates the performance of XML parsing is hurt by the latency but not the throughput of memory subsystem, and thus confirming that prefetching would be effective.

Hardware Cost and Energy Consumption

We summarize the hardware cost of the eight prefetchers in Table 7. On average, these prefetchers require about 28000 bits of memory space. For instance, n6 consists of a 14080 bits L1 prefetcher, a 4096 bits L2 prefetcher and eight 20 bits counters producing 32416 bits hardware cost. All of their hardware cost is below 4KB, which is not a significant amount of hardware resource in modern high-performance processor design. Next we study how these memory-side accelerators impact system energy consumption. Using our simulation framework consisting of CMP$IM and CACTI, we can generate energy parameters of different storage and interconnect structure implemented in different technologies. Here, we focus on the implementation with 32 nm technologies and the results are summarized in Figures 7 and8. In these Figures, we select energy consumption with no prefetching as our baseline, thus a positive number indicates that the prefetcher consumes extra energy, and a negative number indicates otherwise. Note that in 32 nm technology, static energy is comparable to dynamic energy [START_REF]Performance: The 90 nm Inflection Point[END_REF]. The prefetchers generate extra memory requests and bus transactions, thus adding dynamic energy consumption. On the other hand, prefetchers accelerate XML parsing execution, resulting in reduction of static energy consumption. If the static energy reduction surpasses the dynamic energy addition, then the prefetcher results in overall system energy reduction.

As shown in Figure 7, in SAX parsing, most prefetchers lead to more energy consumption: It is due to the increase of dynamic energy dissipation coming from excess memory accesses incurred by prefetching. Nevertheless, looking into details, n5 always leads to energy efficiency, resulting in 1% to 4.5% energy saving across the benchmarks. Similarly, n1 results in energy saving in about half of the cases. This is because n1 and n5 are relatively conservative prefetching techniques: they either prefetch at only one cache level or prefetch a small amount data each time.

In Figure 8, we summarize how acceleration impacts energy consumption in DOM parsing. Identical with Figure 7, n5 is still the most energy efficient prefetcher which archives 12.77% energy saving in mystic-library. Even when running its worst case, resume_w_xsl, n5 can still reduce overall energy by almost 3%. Different from the results in SAX parsing, most prefetchers become energy-efficient in many cases due to their ability to further reduce execution time in DOM parsing. Note that static energy is the product of static power and time, since static power is constant, by reducing execution time, we can reduce static energy as well.

Conclusions

XML has been adopted in cloud computing environments to address the data exchange problem. While XML has brought many benefits, XML parsing also imposes heavy performance penalties. As XML processing often resides at the data exchange frontend, different parts of the system would have dependency on the outputs of XML parsing, making it critical to system performance. While previous research work has focused on computation acceleration of XML parsing, we have identified memory access as one of the performance bottlenecks. Motivated by this finding, in this paper, we have done a study on the effectiveness and feasibility of memory-side acceleration of XML parsing. The results are encouraging, we have demonstrated that memory-side acceleration is effective regardless of the parsing model and is able to reduce cache miss by up to 80%, which translates into up to 20% of performance improvement.

On implementation feasibility, we have identified that XML parsing performance is hurt by the latency but not by the throughput of the memory subsystem, thus verifying that memory-side acceleration is not likely result in resource contention. In addition, we have shown that the memory-accelerators require an insignificant amount of extra hardware resources, and more importantly, in many cases they are indeed able to reduce the overall system energy consumption. These results confirm that memoryside acceleration of XML parsing is not only effective but also feasible.

In our vision, cloud computing services can be hosted by one many-core chip, and within this many-core chip, one or more cores act as the Data Exchange Frontend (DEF). Our next step is to incorporate memory-side and computation-side accelerations into the DEF cores and evaluate its performance in many-core environments.

Figure 1 :

 1 Figure 1: SAX and DOM Parsing Flow

Figure 2 :

 2 Figure 2: Managed Execution vs. Native Execution

Figure 4 :

 4 Figure 4: Disk I/O counts and CPU Usage

Figure 5 :Figure 6 :

 56 Figure 5: Performance improvement for SAX parsing

Figure 7 :

 7 Figure 7: Energy consumption of SAX parsing

Figure 8 :

 8 Figure 8: Energy consumption of DOM parsing

Table 1 : benchmarks

 1

	Name	Size (KB)	Description
	long	65.7	sample XML SOAP file
	mystic-library	1384	Information of library books
	personal-shema	1.4	personal information data
	physics-engine	1171	configuration data for physics simulation
	resume_w_xsl	51.8	personal resume
	test-opc	1.8	xml test file for web services gateway
	Standard	113749	bank transaction records

Table 2 :

 2 Summary of Prefetchers

		Cache Hierarchy	Prefetch Degree	Trigger L1	Trigger L2
	n1	L1 & L2	dynamic	Miss	Access
	n2	L1	Static	Miss	N/A
	n3	L1 & L2	dynamic	Miss	Miss
	n4	L1	Static	N/A	N/A
	n5	L2	Static	N/A	Miss
	n6	L1 & L2	dynamic	Miss	Miss
	n7	L2	Static	Miss	Access
	n8	L2	Static	N/A	Access

Table 3 :

 3 Simulation Parameters

	Frequency	1 GHz
	Issue Width	4
	Instruction Window	128 entries
	L1 Data Cache	32KB, 8-way, 1cycle
	L1 Inst. Cache	32 KB, 8-way, 1cycle
	L2 Unified Cache	512 KB, 16-way, 20 cycles
	Main Memory	256 MB, 200 cycles

Table 4

 4 Cloud Storage; and for each category, we measured the data exchange throughput of four service providers. Note that CDN services contain several copies of data in network to maximize bandwidth, whereas Cloud Storage services provide online storage where people can require their storage capacity for their data hosting needs. On average, the data exchange throughput to CDN services can reach 29.26 Mb/s. When employing the CDN service provided by Amazon CloudFront, the rate can reach 48.85 Mb/s. On the other hand, the average data exchange throughput to Cloud Storage services is 12.56 Mb/s and its best case, provided by Amazon S3 -US East, can reach 21.8 Mb/s. In our experiment, our machine contains a 100 MB/s Network Interface Card and network it connected to has a bandwidth limit of 100Mb/s, which is far greater than the throughput provided by cloud data services. That indicates the network I/O interface is not fully utilized, and thus the network interface is not likely to be the bottleneck of XML parsing operations.

	,we summarize our

Table 4 :

 4 Cloud Service Data Rate

	CDN Service	Cloud Storage Service
	Provider	Rate (Mb/s)	Provider	Rate (Mb/s)
	Akamai CDN	27.50	Amazon S3 -US East	21.80
	Amazon CloudFront	48.85	Amazon S3 -US West	10.31
	Cotendo CDN	27.72	Azure-South Central US	6.97
	Highwinds CDN	12.97	Nirvanix SDN	11.17
	AVG	29.26	AVG	12.56

Table 5 :

 5 Cache Miss Reduction

		n1	n2	n3	n4	n5	n6	n7	n8
	SAX	0.69	0.43	0.82	0.82	0.51	0.4	0.73	0.77
	DOM	0.77	0.52	0.85	0.85	0.61	0.52	0.77	0.84
	Cache Level	L2	L1	L2	L1	L2	L2	L2	L2

Table 6 :

 6 bandwidth consumption without prefetching

		SAX	DOM
	long	4.09%	5.55%
	mystic-library	4.38%	7.46%
	personal-shema	4.94%	6.31%
	physics-engine	4.07%	6.08%
	resume_w_xsl	0.97%	1.03%
	test-opc	1.01%	5.25%
	Standard	6.58%	6.89%

Table 7

 7

			: hardware cost of prefetcher
	n1	32036 bits n2	20329 bits n3	20787 bits n4	30592 bits
	n5	25480 bits n6	32416 bits n7	30720 bits n8	32768 bits

Acknowledgements

This work is supported in part by the National Science Foundation under Grant No. CCF-1065448, the National Natural Science Foundation of China under Grant No. 61070029, as well as the China Scholarship Council.

Any opinions, findings, and conclusions as well as recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the funding agencies.


Xiaohang Wang

Maurizio Palesi
email: maurizio.palesi@unikore.it

Mei Yang

Yingtao Jiang
email: yingtao@egr.unlv.edu

Michael C Huang
email: michael.huang@rochester.edu

Peng Liu
email: liupeng@zju.edu.cn

Power-Aware Run-Time Incremental Mapping for 3-D Networks-on-Chip

Keywords: Networks-on-chip, application mapping, 3-D IC. 1

3-D Networks-on-Chip (NoCs) emerge as a powerful solution to address both the interconnection and design complexity problems facing future Systems-on-Chip (SoCs). Effective run-time application mapping on a 3-D NoC-based Multiprocessor Systems-on-Chip (MPSoC) can be quite challenging, largely due to the fact that the arrival order and task graphs of the target applications are not known a priori. This paper presents a power-aware run-time incremental mapping algorithm for 3-D NoCs that aims to minimize the communication power for each incoming application as well as reduce the impact of the mapped applications on future applications that are yet to be mapped. In this algorithm, if the vertical links are found to be shorter and provide higher communication bandwidth than horizontal links, more communications will be mapped to vertical links to reduce delay and power consumption. Extensive experiments have been conducted to evaluate the performance of the proposed algorithm and the results are compared with those obtained from the optimal mapping algorithm (branch-and-bound), a random mapping and a simple heuristic. When mapping a single application, the proposed algorithm is four orders of magnitude faster than the branch-andbound algorithm at a small degradation of mapping quality. When mapping multiple applications incrementally, our algorithm can save 50% communication power compared to the random mapping and 20% communication power compared to the simple heuristic.

Introduction

Advance in CMOS technology keeps driving the increase of the number of processing cores that can be integrated on a single chip. With the further increase of the number of processing cores, the integration limitations of SoCs become more significant. 3-D integration together with the NoC design paradigm provide a promising solution to overcome these limitations [START_REF] Pavlidis | 3-D topologies for networks-on-chip[END_REF]. In the literature, several approaches exist for 3-D integration, e.g., wire bounded, microbump, through via and contactless [START_REF] Davis | Demystifying 3D ICs: the pros and cons of going vertical[END_REF]. 3-D

Related Work

Research in 3-D NoCs emerges in recent years. In [START_REF] Pavlidis | 3-D topologies for networks-on-chip[END_REF], both the analytical model of zero-load latency and the power model for 3-D NoCs are provided. Different 3-D NoC designs are shown in [START_REF] Matsutani | Tightly-coupled multi-layer topologies for 3-D NoCs[END_REF][START_REF] Feero | Networks-on-Chip in a three-dimensional environment: a performance evaluation[END_REF][START_REF] Park | MIRA: a multi-layered on-chip interconnect router architecture[END_REF]. In [START_REF] Matsutani | Tightly-coupled multi-layer topologies for 3-D NoCs[END_REF], a three-layer NoC is proposed where each layer has different network topology so that the planar topology on every layer could be customized to meet different cost-performance demands. In [START_REF] Feero | Networks-on-Chip in a three-dimensional environment: a performance evaluation[END_REF], both 3-D meshbased architectures (symmetric 3-D mesh, stacked mesh, and ciliated mesh) and 3-D tree-based architectures are analyzed in terms of network performance and energy dissipation. The analysis shows that 3-D mesh-based architectures demonstrate significant performance gains with a small area overhead compared with 2-D meshes. In [START_REF] Kim | A novel dimensionally-decomposed router for on-chip communication in 3D architectures[END_REF], the 3-D Dimensionally-Decomposed (DimDe) Router is proposed. The DimDe router features is a true 3D crossbar with two vertical interconnects spanning over all layers. As such, the crossbars of all the routers with the same vertical index are fused into one unit. With the fusion of crossbar, short vertical links could be utilized such that vertical transmissions among different layers only take one hop. In addition, the crossbar is decomposed to reduce complexity. Simulation results show that the 3-D mesh NoC constructed with DimDe routers achieves better throughput, latency and energy-delay product compared with a symmetric 3-D mesh built with 7port routers extended from 5-port routers [START_REF] Kim | A novel dimensionally-decomposed router for on-chip communication in 3D architectures[END_REF].

In the literature, a number of IP mapping algorithms have been proposed for 2-D NoCs with the objective of minimizing the overall communication power. However, most of these existing mapping algorithms designed for 2-D NoCs summarized in [START_REF] Wang | A power-aware mapping approach to map IP cores onto NoCs under bandwidth and latency constraints[END_REF] cannot be used in run-time incremental mapping for 3-D NoCs as these algorithms do not consider the short vertical links featured in 3-D NoCs. The branch-and-bound algorithm [START_REF] Land | An automatic method for solving discrete programming problems[END_REF] [START_REF] Hu | Energy-and performance-aware mapping for regular NoC architectures[END_REF] can be extended to run-time incremental mapping for 3-D NoCs. However, the extremely long running time is not suitable for run-time mapping. In [START_REF] Addo-Quaye | Thermal-aware mapping and placement for 3-D NoC designs[END_REF], a genetic algorithm based thermal-aware 3-D offline mapping is proposed. Due to the complexity, it is also not suitable for run-time 3-D NoC mapping.

In terms of run-time incremental mapping for 2-D NoCs, several schemes have been proposed. In [START_REF] Smit | Run-time assignment of tasks to multiple heterogeneous processors[END_REF], a run-time task assignment algorithm is proposed for heterogeneous processors with the task graphs limited to a small number of tasks. A dynamic task mapping scheme is proposed for NoC-based MPSoCs in [START_REF] Carvalho | Heuristics for dynamic task mapping in NoC-based heterogeneous MPSoCs[END_REF], aiming to improve the performance by minimizing the channel load. The incremental mapping algorithms proposed for 2-D NoCs [START_REF] Chou | Run-time task allocation considering user behavior in embedded multiprocessor networks-on-chip[END_REF][START_REF] Chou | Energy-and performance-aware incremental mapping for networks on chip with multiple voltage levels[END_REF] may be helpful for 3-D NoCs. The general idea of these run-time mapping algorithms is to find a convex tile region first, followed by mapping the incoming application to the convex region. The convexity of the tile region helps to reduce communication within the region and the impact on future applications as the remaining tiles always form a continuous shape.

Run-time mapping algorithms in traditional parallel and distributed systems [START_REF] Lo | Noncontiguous processor allocation algorithms for mesh-connected multicomputers[END_REF] do not suit for the on-chip application mapping as they do not consider on-chip power consumption.

Problem Formulation

In this paper, our study is focused on run-time mapping for 3-D mesh-based NoCs considering the regularity and advantage of the topology [START_REF] Feero | Networks-on-Chip in a three-dimensional environment: a performance evaluation[END_REF]. Fig. 1 shows the 3-D mesh-based NoC architecture, which is composed of N layers of IP cores and routers.

Each IP core is indexed by (x, y, z) where 0 ≤ x ≤ M x , 0 ≤ y ≤ M y and 0 ≤ z ≤ N-1, (each layer is composed of a M x x M y mesh). At each layer, each IP core is on a single physical plane and connected to its router through a horizontal link. Due to its advantages, the 3-D DimDe router [START_REF] Kim | A novel dimensionally-decomposed router for on-chip communication in 3D architectures[END_REF] is adopted here. As shown in Fig. 1, each router still has five horizontal ports, i.e., E, W, N, S and local. The guided flit queuing methods [START_REF] Kim | A novel dimensionally-decomposed router for on-chip communication in 3D architectures[END_REF] are used to decompose the traffic into X, Y, and Z dimensions. The 5x5 crossbar in a 2-D mesh is split into two 4x2 crossbars to reduce the router complexity.

Each vertical link has one input connection from its associated path set (PS) MUX and three output connections, one to the East-West crossbar, the North-South crossbar and the local port, respectively. Assume that the wire length of vertical links between adjacent layers is much shorter than the wire length of horizontal links between adjacent routers. The deterministic XYZ routing is assumed. A tile is defined to be an IP core with the corresponding part of the router on the same layer.

Guided flit queuing

Path set (PS)

Communication Power Model

The communication energy needed for sending a flit from a source tile to a destination tile is composed of two parts, the energy consumed at the routers and the energy consumed on the interconnection links. The average energy consumption of sending one bit of data from tile t i to tile t j can be represented as

, i j t t bit E =E R + E L (1)
where E R and E L are the energy consumed by the routers and links in the communication path from tile t i to tile t j . To be more specific,

, i j t t bit Rbit H LHbit V LVbit E E E E η η η = + + (2)
where E Rbit is the energy consumed when transporting a flit at the router, η is the number of routers traversed from tile t i to tile t j , H η and V η are the number of horizontal and vertical links in the communication path, and E LHbit and E LVbit are the energy consumed on the horizontal and vertical links between tiles t i and t j . Following the wire model given in [START_REF] Matsutani | Tightly-coupled multi-layer topologies for 3-D NoCs[END_REF], E Lbit =dV 2 C wire /2, where d is the length of the link, V is the supply voltage and C wire is the wire capacitance.

Application and Architecture Model

Each incoming application is represented by its communication trace graph defined below. Definition 1 A Communication Trace Graph (CTG) G=(P, E) is an undirected graph, where a vertex/node p k ∈P represents a task, and an edge e i =(p j , p k )∈E represents the communication trace between vertices p j and p k.

• For edge e i , ω(e i ) defines the communication bandwidth request between vertices p j and p k given in bits per second (bps).

• ω(e i ) sets the minimum bandwidth that should be allocated by the network in order to meet the performance constraints. The 3-D NoC architecture is modeled by the architecture characteristic graph. Definition 2 An Architecture Characterization Graph (ACG) G′=(T, L) is an undirected graph, where each vertex t i ∈T represents a tile and each edge l i ∈L =(t j , t k ) represents the link between adjacent tiles t j and t k . N is the number of NoC layers. For link l i • bw(l i ) defines the bandwidth provided on link l i between adjacent tiles t j and t k ;

• c(l i ) defines the link cost of l i , i.e., power consumption for transmitting one bit data from t j and t k .

In this paper, we focus on NoC architectures which have bw

(l i )=B, c(l i )=C V if l i is a vertical link, c(l i )=C H if l i is a horizontal link for each l i ∈L, where B, C V and C H are constants. , j k t t
h j is the set of links forming one of the shortest paths from tile t j to tile t k ( , j k t t h ⊆ L). We also assume that the IP core with index (0, 0, 0) manages the whole mapping process.

Problem Description

The 3-D NoC run-time mapping problem is described as: Given the CTG of the incoming application and the ACG of the current 3-D NoC system, find a mapping function M:P T, with the objective of minimizing the communication power, i.e., ( ) , ( )

( ) , ( ) | | | | 1 0 0 ( , ) ( ( ) ( ) ) M p M p j k i j k k M p M p j k h E i m i m e p p E l h Min e c l ω - = = = ∈ ∈ ⋅ ∑ ∑ (3)
satisfying

j p P ∀ ∈ , M( j p )∈ T, (4)
,

j k p p P ∀ ∈ and j k p p ≠ , M( j p ) ≠ M( k p ), (5)
∀ l m , B ≥ ( ), ( ) ( , ) ( ) ( , ) j k i j k i m Mp Mp e p p e f l h ω = ⋅ ∑ , (6) where ( ), ( ) ( ), ( ) ( ), ( ) 1 0
( , )

j k j k j k m M p M p m M p M p m M p M p if l h if l h f l h ∈ ∉ ⎧ ⎪ = ⎨ ⎪ ⎩ .
Conditions given by ( 4) and ( 5) ensure that each task should be mapped exactly to one tile and no tile can host more than one task. The inequities given in (6) specify the bandwidth constraint for every link.

4

Motivating example and Problem Decomposition

Motivating Example

A motivating example of mapping a newly incoming application to a 3-D mesh-based NoC (with 3x16 tiles) is given in Fig. 2 to illustrate the composition of the problem. Fig. 2(a) gives the CTG of an example application with 16 tasks. The black tiles in Fig. 2(b) are reserved for other applications already running in the system. Before mapping, as in run-time incremental mapping for 2-D NoCs [START_REF] Chou | Run-time task allocation considering user behavior in embedded multiprocessor networks-on-chip[END_REF][START_REF] Chou | Energy-and performance-aware incremental mapping for networks on chip with multiple voltage levels[END_REF], a region of available tiles shall be selected. Intuitively, a cuboid region is preferred to minimize the impact to future applications. Fig. 2(b) shows such a region of 18 tiles (in grey color). Next, in the mapping process, the tasks which have high communication requests should be considered first [START_REF] Wang | A power-aware mapping approach to map IP cores onto NoCs under bandwidth and latency constraints[END_REF]. Based on the definitions in Section 3, these tasks shall be allocated to the sub-regions in different layers such that the communications with high bandwidth requests can utilize vertical links. Fig. 2(c) shows an allocation result of the tasks which have high communication requests. Last, all tasks are mapped to the tiles in the sub-regions as shown in Fig. 2(d).

A Mapping Flow by Problem Decomposition

Based on the observations from this example, the run-time mapping problem for 3-D NoCs is divided into three sub-problems as shown in Fig. 3. The three sub-problems are described below.

1) NoC Region Selection

First, a region is selected to map each incoming application. This region is composed of N sub-regions, one on each layer. To reduce the impact on future applications, these sub-regions should be rectangle in shape and the size of each of the sub-regions shall be made as close to each other as possible.

Given the CTG of the incoming application, the ACG of the 3-D NoC, and the current system behavior (i.e. the used and unused tiles), this sub-problem is to find a cuboid region SR={SR 0 , …, SR N-1 }, where SR w represents the sub-region of unallocated tiles on layer w, with the objective of:

Min (| SR w | ⋅ N -|G|), for each w=0, …, N-1 (7)
satisfying,

|SR w | ⋅ N ≥ |G|, (8)
|SR w |=|SR w+1 | for w =0, …, N-2, (9)
Here |G| gives the number of tasks in G and |SR w | gives the number of tiles in set SR w .

(P2) Set Matching

The basic idea of set matching is to find the layers to be mapped for those tasks which have high bandwidth (BW) communication requests. When both vertical and horizontal links are available, according to the assumption that vertical links tend to be shorter than horizontal links, vertical links are thus preferred. That is, communication edges with high BW requests shall be allocated to vertical links if possible in order to reduce delay and power consumption.

Assume the edges in G are sorted in a non-increasing order in terms of their communication bandwidth request (i.e., ω(e i )). Let SG ⊂ G be a sub-graph formed with the first α% edges in the sorted edge list [START_REF] Wang | A power-aware mapping approach to map IP cores onto NoCs under bandwidth and latency constraints[END_REF]. The objective is to allocate the vertices in SG into N subsets to be mapped to the corresponding N sub-regions found in (P1) such that the vertical links are used as much as possible. This sub-problem is formally defined as follows.

Given the sub-graph SG of the CTG and the sub-regions SR 0 , …, SR N-1 obtained from region selection step described in (P1), allocate the vertices in SG into N sets SG 0 , …, SG N-1 , assuming vertical links are preferred, with the objective of:

Max ( , ) ( ) i j k j u k v i e p p p SG p SG u v e ω = ∈ ∈ ≠ ∑ , ( 10
)
satisfying,

SG u ∩ SG v = ∅ , for u ≠ v ( 11
)
|SG u | ≤ |SR w |, for each u=0,…, N-1 ( 12
)

(P3) CTG to NoC Region Mapping

With the sub-regions and sets obtained in (P1) and (P2), the application is then mapped to minimize the communication power.

Given the CTG of the incoming application, N sets of the vertices SG 0 , …, SG N-1 and a set of sub-regions SR={SR 0 , …, SR N-1 }, find a mapping function M: P SR with the objective:

Min | | 0 ( , ) ( ( )[ ( ( ) , ( ) ) i j k E i v j k V i e p p E e MD M p M p C ω = = ∈ ⋅ ⋅ ∑ ( ( ), ( )) ]) H j k H MD M p M p C + ⋅ , ( 13
)
satisfying j p P ∀ ∈ , M( j p )∈ T, ( 14
) , j k p p P ∀ ∈ and j k p p ≠ , M( j p ) ≠ M( k p ), ( 15
) ∀ l m , B ≥ ( ), ( ) ( , ) ( ) ( , ) j k i j k i m Mp Mp e p p e f l h ω = ⋅ ∑ , (16) where ( ), ( ) ( ), ( ) ( ), ( ) 1 0
( , )

j k j k j k m M p M p m M p M p m M p M p if l h if l h f l h ∈ ∉ ⎧ ⎪ = ⎨ ⎪ ⎩
, MD H () and MD V () denote the horizontal and vertical Manhattan distance between two tiles, respectively. Conditions given by ( 14) and ( 15) ensure that each task should be mapped exactly to one tile and no tile can host more than one task. The inequities given in ( 16) specify the bandwidth constraint for every link.

Algorithm Description

For each sub-problem listed in Section 4, an algorithm is introduced in each of following subsections. Before discussing these algorithms, the following assumption is made. All the edges of an incoming application's CTG are sorted in a decreasing order by the edge weight ω(e i ). The sorted edge list is represented as SE.

NoC Region Selection (P1)

As discussed in Section 4, a cuboid of NoC tiles shall be first found. This problem can be further divided into two small problems. First, given the incoming application's CTG G, a window with a size of size l•w should be found such that N•l•w ≥ |G| and N•l•w -|G| is minimized. That is, the shape and size of sub-region should be chosen to minimize fragmentation. Second, after finding the l•w matrix, unallocated tiles which form the N•l•w cuboid should be found (these tile regions are called NoC regions). A window sweeping process is used as in Fig. 4(a).

A window of size l•w starts from tile (0, 0, 1) and moves at the first layer. The window sweeps the whole layer until all of the tiles inside the window are found not allocated yet.

An example of applying this algorithm is shown in Fig. 2(b). The CTG shown in Fig. 2(a) has 16 tasks. Thus, a 3x2x3 cuboid is selected based on the window sweeping process (Fig. 2(b)).

The NoC region selection algorithm is shown in Fig. 4

Set Matching (P2)

In the second step, the sub-graph of the CTG, i.e. SG, which includes the tasks with high communication BW requests should be allocated into the N sets, one for each layer. The sub-graph SG is formed by the first 50% edges (denoted as SE′) in SE, Vertical links are preferred for high BW communication edges. Hence, edges with larger weight will be first allocated to vertical links if possible. However, there is only one vertical link between the two tiles (x, y, z) and (x, y, z+1), z= 0, …, N-2. Thus, if a task is allocated to tile (x, y, z) and has two neighbors in layer z+1, it may result in higher power consumption than mapping one of the neighbors to the same layer z. Fig. 5 shows such an example. Given the CTG shown in Fig. 5(a), if tasks 1 and 2 are mapped to layer 1 (Fig. 5(b)), the energy cost is 10•(C V +C V +C H ) suppose the link energy cost are C V and C H for vertical and horizontal links, respectively. If task 2 is mapped to the same layer of task 0 (Fig. 5(c)), the energy cost is 10•(C V +C H ) which is lower than that of Fig. 5(b). Thus, an observation is made that when vertical links are preferred, a task can be allocated to the same layer of its neighbor if the neighbor already has edges allocated to adjacent layers. The algorithm works as follows. For each edge (p j , p k ) in the sorted edge list SE′,

• If neither of the two tasks is allocated, the tasks are checked to see whether one of them has degree in SG greater than 1. If so, the task with a larger degree in SG is allocated to SG u with (0<u<N-1), i.e., to a layer whose tiles have two vertical links, up and down. Otherwise, the tasks are allocated to SG u and SG v with u ≠ v and |u-v| minimized. • If one of the tasks is allocated, e.g., p j is allocated to SG u , the unallocated task p k is allocated to SG v (u ≠ v) such that |u-v| is minimized, given that p j has no neighbor in SG v . Otherwise, p k is allocated to SG u .

Fig. 6 shows an example of the set matching processing based on the CTG given in Fig. 2(a). The sub-graph SG of this CTG is given in Fig. 6(a) and the size of region on each layer is 6. The sorted edge list of the sub-graph is {(0, 1), (0, 2), (1, 5), [START_REF] Davis | Demystifying 3D ICs: the pros and cons of going vertical[END_REF][START_REF] Chou | Energy-and performance-aware incremental mapping for networks on chip with multiple voltage levels[END_REF], [START_REF] Smit | Run-time assignment of tasks to multiple heterogeneous processors[END_REF][START_REF] Lo | Noncontiguous processor allocation algorithms for mesh-connected multicomputers[END_REF], (14, 15)}. Fig. 6(b) shows that tasks 0 and 1 are first allocated to SG 1 and SG 0 as task 0 has a degree of 2 in Fig. 6(a). When allocating edge (0, 2), task 2 is allocated to SG 0 as task 0's neighbor task 1 is already allocated to SG 1 (Fig. 6(c)). When allocating edge (1, 5), task 5 is allocated to SG 0 as task 1's neighbor task 0 is already allocated to SG 1 . Similarly, task 6 is allocated to SG 2 as in Fig. 6(d). Tasks 13, 14 and 15 are allocated similarly as in Fig. 6(e) and (f). The final result of the set matching problem for the vertices in SG is shown in Fig. 6

(f).

The set matching algorithm is shown in Fig. 5(d). The complexity of the algorithm is O(|E||N| 2 ). • If neither of the two tasks p j , p k are mapped. There are three cases to consider 1) Both tasks are already allocated to the N sets SR 0 , …, SR N-1 , e.g., p j allocated to SG u and p k allocated to SG v (0 ≤ u, v ≤ N-1). If p j has high degree (>2) in SG, find a tile in SR u with large number of free neighbor tiles. Otherwise, find an unused tile in SR u for p j . Then find a tile for p k in SR v to minimize the Dist() metric.

2) One of the two tasks already allocated to the N sets, e.g., p j allocated to SG u . If p j has high degree (>2) in SG, find a tile in SG u with large number of free neighbor tiles. Otherwise, find an arbitrary tile in SG u for p j . Then find a tile for p k in SR to minimize the Dist() metric.

3) Neither of the two tasks allocated to the N sets yet. If p j has high degree (>2) in SG, find a tile in SR with large number of free neighbor tiles. Otherwise, find an arbitrary tile in SR for p j . Then find a tile for p k in SR to minimize the Dist() metric. • If one of the two tasks is mapped, e.g., p j is mapped to tile t. If the unmapped task p k is allocated to SG u , find a tile in SR u for p k to minimize the Dist() metric.

Otherwise, find a tile for p k in SR to minimize the Dist() metric.

The CTG to NoC region mapping algorithm is shown in Fig. 7. The complexity of the CTG to NoC region mapping algorithm (P3) is O(|E||T| 2 ). The total complexity of the run-time incremental mapping algorithm (combining the algorithms introduced in section 5.1 to 5.3) is O(|E||T| 2 ).

Fig. 1 .

 1 Fig.1. The 3-D NoC architecture[START_REF] Kim | A novel dimensionally-decomposed router for on-chip communication in 3D architectures[END_REF]

Fig. 2 .

 2 Fig. 2. Illustration of the whole problem.

Fig. 3 .

 3 Fig. 3. The mapping process.

( 4 . 1 .

 41

Fig. 4 .

 4 Fig. 4. The NoC region selection algorithm.

Fig. 5 .

 5 Fig. 5. The set matching algorithm (P2).

Fig. 6 .

 6 Fig. 6. An example of set matching when vertical links are preferred.

5. 3

 3 CTG to NoC Region Mapping (P3)After finding the set of tile regions SR and the allocation of the vertices in SG to the N set SR 0 , …, SR N-1 , all of the vertices in CTG should be mapped to SR. In this algorithm, a metric Dist() is used to find the weighted distance of two tiles. The Dist() metric is defined as: Dist(t a ,t b )=|x a -x b |C H +|y a -y b |C H +|z a -z b |C V , where (x a ,y a ,z a ) and (x b ,y b ,z b ) represent the coordinates of tiles t a and t b , respectively. As discussed in Section 3, Dist() reflects the power consumption of each communication edge after mapping the two tasks. The algorithm checks for each edge in SE of CTG and maps the tasks to minimize their distance. It works as follows. For each edge (p j , p k ),

This work is supported in part by NSFC under the grants 60873112 and 61028004

Assume the vertical links are preferred for communications with high BW requests. Fig. 2(d) shows the mapping result given the CTG in Fig. 2(a) based on the results of NoC region selection (Fig. 2(b)) and set matching (Fig. 2 (c)).

CTG_to_NoC_mapping (G, SE, SR) Input: [START_REF] Pavlidis | 3-D topologies for networks-on-chip[END_REF] G: the CTG of the incoming application

(2) SE: the sorted edge list of the CTG (3) SR: the set of sub-regions for the incoming application (4) SG0, …, SGN-1: the N sets containing the vertices in SG Output: (

Performance Evaluation

The proposed algorithms have been evaluated through extensive experiments. Two sets of experiments are performed. First, single random applications are mapped to a 3-D NoC architecture. In this set of experiments, our algorithm is compared against the branch and bound (BNB) algorithm in terms of the solution quality. BNB tries to exhaustively enumerate all possible mapping results where mapping results with higher power consumption are discarded by estimating upper and lower bounds. Second, multiple applications (including random applications generated by TGFF [START_REF]TGFF: task graphs for free[END_REF] and applications from E3S [START_REF] Dick | Embedded system synthesis benchmarks suite(E3S)[END_REF]) are incrementally mapped to a 3-D NoC architecture. In this set of experiments, our algorithm is compared against a random mapping algorithm and a simple heuristic algorithm, namely large communication first (LCF).

The power model is adopted from the DimDe router [START_REF] Kim | A novel dimensionally-decomposed router for on-chip communication in 3D architectures[END_REF]. The network is assumed to be a 6x6x3 3-D mesh. The flit size is set to be 128-bit. To study the power consumption trend, vertical and horizontal links with different lengths are chosen. The wire parameters are adopted from [START_REF] Pavlidis | 3-D topologies for networks-on-chip[END_REF], e.g., the unit wire capacitances (C wire ) for vertical and horizontal links are 600fF/mm and 332fF/mm, respectively. Table I lists the wire length combinations evaluated where vertical links are preferred over horizontal links. The Noxim simulator [START_REF] Noxim | [END_REF] is used as the NoC simulator.

Mapping Single Application to 3-D NoC

First, we show the single application mapping results of our algorithm compared to that of BNB. Two types of applications are evaluated: random applications and real applications. For random applications, TGFF is used to generate the CTGs. The numbers of tasks range from 12 to 20. The communication BW requests vary from 1 to 10. The tile regions selected for our algorithm and BNB are the same. The running time of BNB is more than one hour while the running time of our algorithm is within 1 sec. From Fig. 8, we can see that the increase in power consumption of our algorithm over BNB is within 11%. Fig. 8 shows that, the results from our algorithm get closer to that of BNB when the energy cost ratio of horizontal links over vertical links (C H :C V ) are smaller. The ratio of C H :C V is the largest for combination I and smallest for combination VI. The reason is due to the fact that, as the ratio of C H :C V becomes smaller, the difference in vertical and horizontal communications is reduced. The power consumption of horizontal links in the mapping result produced by our algorithm has less impact on the overall communication power consumption.

Mapping Multiple Applications Incrementally to 3-D NoC

In this section, our algorithm is compared against a random mapping (RM) and large communication first (LCF) with multiple applications. Due to the complexity of BNB, it is not used for runtime mapping. In RM and LCF, the NoC region selection step is the same as in our algorithm. RM maps the tasks to the tiles in the selected region randomly. LCF sorts the edges in the non-increasing order of BW request. Then the terminal vertices of the communication edge with higher bandwidth request are mapped to links with smaller c(l) values. Both random and real applications are evaluated.

First, random applications are simulated with their CTGs generated from TGFF [START_REF]TGFF: task graphs for free[END_REF]. The numbers of tasks in these CTGs vary from 12 to 20. The communication BW requests vary from 1 to 10. For each combination in Table I, five experiments are performed for each number of tasks. In each experiment, 10 applications are mapped to a 6x6x3 network. The running time of each application is varied from 1 to 10 time units. Fig. 9 shows the normalized power saving of our algorithm over RM and LCF. Fig. 9(a) shows that our algorithm can save up to over 50% power compared to RM and up to 20% over LCF.

Real application CTGs, including auto-industry, consumer, networking, and office automation, are generated from E3S [START_REF] Dick | Embedded system synthesis benchmarks suite(E3S)[END_REF]. Again, for each combination in Table I, five experiments are conducted. Each experiment is composed of 10 applications which are mapped to a 6x6x3 network incrementally. Fig. 9(b) shows that our algorithm can save up to about 30~40% power compared to RM and up to 8~17% compared to LCF. The power saving in Fig. 9(b) is smaller than that in Fig. 9(a) since the CTG structures of the real applications from E3S are highly regular, e.g., mostly forming a chain-type structure. For such chain-type CTGs, RM and LCF will result in better results compared to non-regular structures. Power consumption are normalized over the power consumtiopn of the results of our algorithm.

Conclusion

In this paper, we have proposed a power-aware run-time incremental mapping algorithm for 3-D NoCs with the objective of minimizing the communication power for each incoming application. In addition, the proposed algorithm attempts to reduce the fragmentation impact on future applications. The proposed algorithm is composed of three steps: 1) NoC region selection which selects a cuboid region to reduce the impact to future applications, 2) set matching which allocates the application graph to the sub-regions in different layers such that the vertical links are used as much as possible, 3) CTG to NoC region mapping which maps the tasks to the tiles in different sub-regions with minimized total communication power. Our experiment results have confirmed that the proposed algorithm is over four orders of magnitude run time efficient than BNB when mapping a single application. It has been shown that our algorithm can also achieve 50% power saving compared to random mapping and 20% compared to a simple heuristic when mapping multiple applications incrementally.