Majid Sabbagh
email: msabbagh@ece.neu.edu

Hamed Tabkhi
email: tabkhi@ece.neu.edu

Gunar Schirner
email: schirner@ece.neu.edu

Taming the Memory Demand Complexity of Adaptive Vision Algorithms

With the demand for utilizing Adaptive Vision Algorithms (AVAs) in embedded devices, serious challenges have been introduced to vision architects. AVAs may produce huge model data traffic while continuously training the internal model of the stream. This traffic dwarfs the streaming data traffic (e.g. image frames), and consequently dominates bandwidth and power requirements posing great challenges to a low-power embedded implementation. In result, current approaches either ignore targeting AVAs, or are limited to low resolutions due to not handling the traffics separately. This paper proposes a systematic approach to tackle the architectural complexity of AVAs. The main focus of this paper is to manage the huge model data updating traffic of AVAs by proposing a shift from compressing streaming data to compressing the model data. The compression of model data results in significant reduction of memory accesses leading to a pronounced gain in power and performance. This paper also explores the effect of different class of compression algorithms (lossy and lossless) on both bandwidth reduction and result quality of AVAs. For the purpose of exploration this paper focuses on example of Mixture-of-Gaussians (MoG) background subtraction. The results demonstrate that a customized lossless algorithm can maintain the quality while reducing the bandwidth demand facilitating efficient embedded realization of AVAs. In our experiments we achieved the total bandwidth saving of about 69% by applying the Most Significant Bits Selection and BZIP as the first and second level model data compression schemes respectively, with only about 15% quality loss according to the Multi-Scale Structural Similarity (MS-SSIM) metric. The bandwidth saving would be increased to 75% by using a custom compressor.

Introduction

The demand for vision capabilities in embedded devices is rising more than ever. Embedded devices, ranging from tiny medical implants to smart cars and distributed smart cameras, need advanced vision capabilities and visual scenes analysis. Among different types of vision algorithms, the need is toward the algorithms that can dynamically adapt to the varying scene conditions. AVAs are considered as the dominating class of algorithms for advanced visual analysis. They are based on the machine-learning principles and are able to capture the runtime changes in the scene (e.g. MoG background subtraction and Support Vector Machine (SVM)).

While AVAs have been realized for fairly long time in algorithm-development environment (e.g. Matlab), their embedded low power realization is still very challenging.

Embedded devices are bounded in computation/communication resources with limited energy/power budget. In contrast, AVAs demand for a significant computation and communication capabilities which results in a power consumption far beyond the embedded system budgets. Realization of computation through custom design and High-Level Synthesis is well-formulated. On the other hand, communication appears as the primary bottleneck hindering implementation of AVAs on embedded devices.

The main limitation of AVAs is significant communication traffic imposed by algorithm itself. Due to inherent learning properties of AVAs, they maintain and continuously update model data of the scene. The model data is algorithm-intrinsic and its existence is independent of algorithm implementation. The size of model data is often very large exceeding the capacity of today's on-chip memories, forcing the designers to utilize off-chip memory. In result, accessing and updating the model data results in huge off-chip bandwidth demand and its associated power consumption. For instance, the bandwidth demand for updating the MoG background subtraction algorithm at Full-HD resolution is about 8GB/s, based on the analysis of the standard OpenCV algorithm. This contributes to about 90% of total power consumption [START_REF] Tabkhi | Power-efficient real-time solution for adaptive vision algorithms[END_REF]. Therefore, to open efficient realization of AVAs on embedded devices, the first step is to manage huge communication demands associated with the model data.

Existing approaches often ignore embedded realization of AVAs and focus on the non-adaptive ones, or only implement AVAs at very low resolutions (300*400) [START_REF] Xu | A case study in networks-on-chip design for embedded video[END_REF][START_REF] Lv | A methodology for architectural design of multimedia multiprocessor socs[END_REF][START_REF] Chen | Energy savings through compression in embedded java environments[END_REF]. However, current trend is toward utilizing AVAs to deliver advanced vision capabilities at Full-HD resolution (1920*1080). Overall, optimizing the model data has received less attention despite being crucial for real-time low-power implementations of AVAs. The need is toward systematic approaches that can provide a guideline on how to efficiently manage model data communication traffic. This paper introduces a system level approach for taming the memory demand complexity of Adaptive Vision Algorithms. The main goal of this research is to open a path toward efficient management of model data traffic. By focusing on model data, we explore the opportunity of shifting the current trend in compressing the streaming data (i.e. applying different video/image encoding methods), toward compressing the model data to reduce the bandwidth and power. Following a system-level approach, this paper also explores the effect of different classes of compression algorithms, lossy and lossless, on both bandwidth reduction and resulting quality. Based on the observations, this paper offers design choices and trade-offs for finding the best compression methods.

For the purpose of exploration, this paper focuses on the example of MoG background subtraction [START_REF] Stauffer | Adaptive background mixture models for real-time tracking[END_REF]. Our results on the example of MoG demonstrate 50% reduction in communication bandwidth by applying a lossy linear compression (Most Significant Bits selection) with minimal quality loss. A higher bandwidth saving 69% can be achieved by BZIP general-purpose lossless compression with no quality loss. Further bandwidth saving is also achieved by a customized compression scheme (e.g. 75% in [START_REF] Ratnayake | Embedded architecture for noise-adaptive video object detection using parameter-compressed background modeling[END_REF]). This paper is organized as following: Section 2 overviews relevant prior work. Section 3 briefly provides background and additional motivation. Following that, Section 4 describes our systematic approach for bandwidth quality trade-off on different class of compression algorithms. Section 5 concludes the paper and touches on future work.

Related Work

The embedded realization of vision algorithms is still at early stages. Most of the previous work on embedded vision have been bounded to basic vision filters, e.g., Canny edge detection, with regular computation and much less communication demand [START_REF] Xilinx | Programming vision applications on zynq using opencv and high-level synthesis[END_REF][START_REF] Tang | Canny edge detection codec using vlib on davinci series dsp[END_REF]. Only few researchers have targeted adaptive vision algorithms (e.g., MoG, KLT, optical flow) on embedded devices. What all previous approaches share in common is lack of insight about source and nature of the traffic. Therefore, they mainly propose a common communication interface for transferring all types of data. Thus, they either ignore the algorithm-intrinsic traffic, or assume that it is hidden in the communication hierarchy. In the result, their proposed solutions works at low resolutions ( 300*400) which is far below Full-HD resolution (1920*1080) [START_REF] Xu | A case study in networks-on-chip design for embedded video[END_REF][START_REF] Lv | A methodology for architectural design of multimedia multiprocessor socs[END_REF][START_REF] Chen | Energy savings through compression in embedded java environments[END_REF][START_REF] Swaminathan | High speed generic network interface for network on chip using ping pong buffers[END_REF]. However, in [START_REF] Tabkhi | Power-efficient real-time solution for adaptive vision algorithms[END_REF] authors propose Data Separation concept for Adaptive Algorithms, in which the streaming data is handled differently compare to the model data. That helped them to realize the MoG algorithm for background subtraction in Full-HD resolution at 30 frames per second. We based our studies on [START_REF] Tabkhi | Power-efficient real-time solution for adaptive vision algorithms[END_REF] for applying different compression schemes on model data and analyzing its effect on the system performance and output quality.

A recent work [START_REF] Ratnayake | Embedded architecture for noise-adaptive video object detection using parameter-compressed background modeling[END_REF] hints about the significant communication volume of MoG background subtraction algorithm. It also provides a promising lossless compression method which can reduce the bandwidth demand for updating MoG parameters down to 50%. Although their compression method sounds to be very efficient and promising, their approach lacks a holistic approach which studies different compression schemes and can generalize the concept of compression on model data for AVAs.

The general observation is that optimizing the model data has received much less attention despite being crucial for real-time low-power implementation of AVAs. In contrast to previous approaches, this paper focuses on optimizing and managing huge communication demand for updating and accessing model data in AVAs.

Background

This section briefly provides background information on traffic separation in the context of AVAs, and for MoG background subtraction algorithm as an example of AVAs.

Data Separation

Data separation, proposed by [START_REF] Tabkhi | Power-efficient real-time solution for adaptive vision algorithms[END_REF], distinguishes two types of data: streaming data and model data. Fig. 1 highlights these two types of traffic in the context of AVAs. The streaming data (pixels) is the input/output data to the algorithm, while the model data is the intrinsic part of algorithm for realizing targeted processing. In AVAs, typically the model data is much bigger than streaming data. The size of model data exceeds the capacity of today's on-chip memories, forcing the designers to utilize the off-chip memory. Furthermore, since the model data should keep up with the streaming data, the bandwidth demand for reading and writing the model data from/to the memory would be a real limitation. Data Separation provides the opportunity for targeted optimization on both streaming data and model data.

Streaming Data

Streaming Data

Model Data

Adaptive Model

Adaptive Algorithm The traffic separation also streamlines the construction of complete vision flow out of multiple AVAs executing different parts of applications over the streaming data. Each AVA has its own model data which hits the memory hierarchy while streaming data is passed across the kernels. This further motivates us to have a systematic solution toward ever increasing communication complexity of AVAs. The Data Separation insight helps us to explore and tailor the compression opportunities on model data.

MoG Background Subtraction

MoG background subtraction is a very good representative of AVAs [START_REF] Stauffer | Adaptive background mixture models for real-time tracking[END_REF]. In this paper, we also use this algorithm to present our results. MoG is used in vision computing for identifying moving objects from the background scene. Fig. 2 includes the MoG coarse-grain mathematical formulation. MoG uses multiple Gaussian distributions, also called Gaussian components, to model a pixel's background. Each Gaussian component has its own set of Gaussian components: weight ω i , an intensity mean µ i and a standard deviation σ i . In Full-HD resolution, for storing all Gaussian parameters about 74 MB of storage is required which may exceed the on-chip memory capacity available in embedded platforms. As a new pixel arrives, all Gaussian parameters are updated to track BG changes of the pixel at frame basis. On the other hand, the bandwidth demand for updating the Gaussian parameters, assuming 32 bit per Gaussian parameter with 3 Gaussian components per pixel, is about 8 GB/s (for processing at Full-HD resolution 60fps), which is 30 times more than streaming bandwidth, which is 265 MB/s for transferring 16-bit input pixel and 1-bit output foreground mask.

Algorithms Communication Computation

Floating/Fixed Point Comp.

Compression Processing

Coarse-Grain Pipelining Data Sepration

Model Data Compression

Comp/ comm Computation / Communication

Trade-off Synchronization/ Memory Management Figure 3: System-Level design flow starts from analysis of algorithms to identify orthogonal axises of optimization with separated axises for computation and communication. There is a computation/communication trade-off at which point the computation and communication axises meet. The trade-off occurs when compressing the model data adds to the computation demand while reduces the bandwidth demand.

In this study, we mainly focus on communication axis because of significant communication demand in AVAs for periodically accessing and updating the model data. Complexities in computation axis, include but not limited to, multi-dimensional processing, complex operations, floating point computation which can be explored separately and are not part of this study.

Using the data Separation insight, we propose a shift from current trend in compressing streaming data toward compressing model data. As shown in Fig. 4, compression/decompression units could be placed in the access interface of model data, providing the opportunity of significantly reducing the model update bandwidth.

Figure 4: Compression/Decompression on model data access

There are two major categories in compression methods, lossy and lossless. In lossy compression, there is a trade-off between the achievable bandwidth saving and output quality while in the lossless compression schemes there would be no quality loss probably with the cost of higher computation demand. Overall, the primary metrics needed to be considered for choosing a suitable compression algorithm are: (1) achievable bandwidth saving, (2) quality effect (lossy/lossless), and (3) computation demand for compressing/de-compressing model data.

Experimental Setup

For the purpose of study, we focus on MoG background subtraction algorithm explained in Section 3.2. We modeled MoG in SpecC System Level Design Language (SLDL) Decompression unit reads the compressed model data from a file, decompress it, and sends the individual parameters out when the corresponding pixel arrives at input of MoG. Then, after finishing the processing, MoG block outputs foreground masks as the output stream and updated parameters as model data. Model data will be written back to a file after being compressed by the compression unit. In the following section, we will study the effect of applying different compression methods on MoG's model data.

During the exploration, we assess the quality against the ground-truth (MoG with no compressed Gaussian parameters). We use MS-SSIM metric. MS-SSIM focuses on the structural similarity between two frames which is more similar to human perception [START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF]. MS-SSIM quantifies the quality as a value between 0 to 1 where a higher value means closer similarity and thus lower quality loss compared to ground-truth.

Evaluation of Compression Schemes

MSBSel The simplest compression method is to statically select the most significant bits of parameters. We call this method Most Significant Bits Selection (MSBSel). Although MSBSel is a lossy compression, it has almost no computation overhead especially considering a hardware implementation. We call the model with MSBSel compression method the reference model in later explanations. This compression scheme introduces the Quality-Bandwidth trade-off as illustrated in Fig. 6. Based on Fig. 6, the quality and bandwidth have a non-linear relationship and it is possible to reduce bandwidth without quality loss (in the bandwidth range from 160 MB/s down to about 120 MB/s). Moreover, by reducing the bandwidth down to 50%, i.e. 80 MB/s, quality will not drop more than 15% according to MS-SSIM quality metric. Although this is due to the nature of MoG algorithm, but same trend could be observed for other AVAs. Selecting fewer bits leads to higher bandwidth saving but also higher degradation in quality. A high dynamic range or precision is essential for accurate background subtraction. This raises a need for complex/advanced compression algorithms to further reduce the bandwidth requirements for updating model data.

JPEG-2000

To further explore the compression effect on MoG parameters, JPEG-2000 compression applied as the second-level compression after MSBSel to evaluate if it can reduce the bandwidth without affecting the quality significantly. JPEG is a wellknown image compression method developed by Joint Photographic Experts Group [12]. JPEG-2000 is the newer version of JPEG, which also supports 16-bit gray-scale images. The bandwidth saving corresponding to the compression ratio was less than the expected value. For example, the expected bandwidth saving of 10:1 compression ratio, is 90%. However, in practice it is about 85%. The effect of noise on degrading the performance of compression methods is already studied in literature. For example, a study in [START_REF] Lo | Noise impact on error-free image compression[END_REF] shows that noise reduces the inter-pixel correlation which compression ratio increased. Some approaches, such as [START_REF] Cosman | Evaluating quality of compressed medical images: Snr, subjective rating, and diagnostic accuracy[END_REF] and [START_REF] Melnychuck | Effect of noise and mtf on the compressibility of high-resolution color images[END_REF], filters the effect of noise from the source image. However, all based on assumption that feature of filtering solutions is that they consider noise in images as unwanted data. In contrast, the visual distortion that is observable in MoG parameters are actually the values produced by the algorithm and are required in next iteration for computation. Therefore, eliminating the distortion which is seen in MoG parameters in fact reduce the quality of MoG.

To study the effect of JPEG bandwidth saving on the MoG quality (the foreground masks), we compared the output of MOG with JPEG compression against the reference model. The outputs are compared using the MS-SSIM quality metric in a simple scene, with few object movements and variations, and a complex scene, with lots of object movements and crossings. Fig. 9 plots the quality across total bandwidth saving when applying JPEG compression for parameter Mean. The maximum achievable output quality is about 0.46 out of 1, in the simple frame sequence. This is even worse in complex frame sequence which the maximum output quality is 0.22 with bandwidth saving of only 2% on average. With increasing compression rate to further reduce the bandwidth, the quality degradation would be more pronounced reaching to a point which basically MoG is not functional anymore. Overall, we conclude that JPEG-2000 have severe degradation effect on the final output quality of MoG. We can trace back this issue to the adaptive behavior of the MoG algorithm, meaning that since the MoG parameters are recursively accessed and updated, even a small error can accumulate, resulting in degradation of background subtraction robustness and eventually output quality loss. All of these observations motivate us to explore other possibilities for compression of model data, therefore we will look into the opportunity of using lossless compression schemes.

Lossless Compression

The principal feature of lossless compression algorithms is that they do not affect the quality of data being compressed. Therefore, rather than quality loss, the designer may change the focus to other characteristics of compression algorithms, such as the achievable compression ratio and computation demand. In our study, five different lossless compression methods have been explored: QZIP, LZ4, BZIP, GZIP and ZIP. QZIP and LZ4 are two compression algorithms which are in high-speed categories, while BZIP, GZIP and ZIP are three regular compression methods. The experiments are done over 4500 parameter images that are the MoG parameters of 3 Gaussian components, each having 3 parameters (Mean, Standard Deviation and Weight) for 500 frames of original 1024x768 resolution. All of the lossless compression methods are applied as the second level compression after MSBSel. To further explore the granularity of source data which a certain algorithm will operate on, we divide the input frames to smaller blocks. A 1024x768 frame could be divided into 25.6 blocks of 40x30, 12.8 blocks of 80x60, 6.4 blocks of 160x120, 3.2 blocks of 320x240, 1.6 blocks of 640x480 and 1 block of 1024x768 resolution. Fig. 10a presents the average bandwidth saving over different block sizes for all compression algorithms. The maximum bandwidth saving could be achieved, when using the 1024x768 block size. In fact, by reducing the block size to less than 1024x768, all algorithms perform poorly in bandwidth reduction, at the best case reaching to less than 10% bandwidth saving. The best average bandwidth savings captured in lossless experiments is about 38% percent, corresponding to BZIP compression scheme with block size of 1024x768. Fig. 10b shows the average computation demand over different block sizes for all compression algorithms. To estimate the computation demand, we used Pin -Dynamic Binary Instrumentation Tool [START_REF]Pin -a dynamic binary instrumentation tool[END_REF], from Intel. The block size of 1024x768, equal to full image size, leads to largest computation demand. Overall, the computation demand varies across the algorithms. In QZIP and ZIP, the lowest computation demand is achieved by using block size of 80x60, for LZ4 320x240 and for GZIP and BZIP 40x30. Fig. 10a ). In high-compression mode, LZ4 could provide better compression ratio with the cost of higher computation demand. Combining Fig. 10a and Fig. 10b, we can derive Fig. 11 showing the trade-off between bandwidth saving and computation demand. In Fig. 11, the numbers over the stars show the average bandwidth saving, while the crosses show the range of achievable bandwidth demand corresponding to a certain computation demand. For different algorithms, the trend is that lower bandwidth demand or higher bandwidth saving, is achievable by having more computation. Among all algorithms, LZ4 in fastmode has the lowest computation demand, which is about 100 millions instructions for compression and decompression of a frame, and at the same time the lowest bandwidth saving of 17%, while the BZIP achieves highest bandwidth saving of 38% with the highest computation demand of about 1 billion instructions. Note that, computation demand of LZ4 for compression and decompression of a frame in high-compression mode is about 10 times higher than its computation demand in fast-mode.

Custom Compression

The previous studied lossless compression methods are general algorithms developed to compress any sort of data. The results of our experiments illustrate that although there are lots of options for compressing the model data, but for AVAs such as MoG, which have special type of model data produced by statistical and non-linear processing, general purpose image or data compression methods might not provide the desirable performance for designers. There is a demand for lossless compression algorithm customized for compressing model data in context of AVA. This fact, motivates designers such as in [START_REF] Ratnayake | Embedded architecture for noise-adaptive video object detection using parameter-compressed background modeling[END_REF] to devise custom model data compression schemes only for a certain type of algorithm. One preliminary example, has been already proposed by [START_REF] Ratnayake | Embedded architecture for noise-adaptive video object detection using parameter-compressed background modeling[END_REF].

In [START_REF] Ratnayake | Embedded architecture for noise-adaptive video object detection using parameter-compressed background modeling[END_REF], the authors propose a DPCM-based compression algorithm for compression of MoG parameters. Their algorithm, extracts and uses the inter-correlation of parameters for different Gaussian Components of MoG and intra-correlation of parameters for within the Gaussian Components, to represent every two parameters with one compressed parameter, in a lossless process, reducing the bandwidth demand down to 50%. In terms of computation demand, the FPGA implementation of their algorithm shows reasonable resource utilization of about 2282 LUTs and 1876 FFs in Virtex-5 FPGA, without any use of DSP Blocks and more importantly Block RAMs.

Results Summary

To summarize, Using the Data Separation insight, we explored the opportunity of applying different compression schemes on model data, to shift the compression trend from streaming data to model data. During the experiments we evaluated several tradeoffs:

-Lossy Compression compression mode and fast-mode: By using LZ4 in high-compression mode, higher bandwidth saving is achievable with the cost of higher computation demand Overall, by applying BZIP as the second level compression scheme over MSBSel, the total bandwidth saving of about 69% is achievable, while the bandwidth saving could be increased to about 75% by using a custom compressor instead of BZIP. The overall output quality loss would not be more than 15% according to the MS-SSIM metric for both of these cases. These trade-offs could help the system architects for AVAs, choose the right compression algorithm for model data based on the application requirements. Furthermore, designers might have to use or devise tailored algorithms for AVAs' model data, such as the compression method proposed in [START_REF] Ratnayake | Embedded architecture for noise-adaptive video object detection using parameter-compressed background modeling[END_REF] for compressing the MoG parameters.

Altogether, using the Data Separation insight and by applying compression on model data, realization of AVAs could be facilitated as the overall system bandwidth demand became manageable, taming the complexity of AVAs realization. We would consider power consumption in future works as it is a very important factor in embedded systems, while in this work we focus on evaluating the compression ratio and computation demand in lossless compression schemes.

Conclusions

This paper proposes a systematic approach for tackling the complexity of AVAs. We focus on the main challenge which is the communication complexity due to huge bandwidthdemand for updating model data in AVAs. Using the Data Separation insight and by applying compression on model data, realization of multiple vision kernels could be facilitated on a single platform. Also, throughout our study we evaluated different lossy and lossless compression algorithms, providing the system architects with various trade-offs and intuitions for choosing the right method of compression for model data.

Figure 1 :

 1 Figure 1: Streaming data vs model data

Figure 2 :

 2 Figure 2: Memory Access per Pixel in MoG algorithm

FileFigure 5 :

 5 Figure5: High-level diagram of evaluation model for MoG[START_REF] Gerstlauer | System Design: A Practical Guide with SpecC[END_REF]. The high-level diagram of the experimental model is shown in Fig.5. The stream of input pixels will be fed from stimulus block to MoG which at the same time receives the corresponding parameters, i.e. model data, from the Read Param block. Read Param block receives the decompressed parameters from the decompression unit. Decompression unit reads the compressed model data from a file, decompress it, and sends the individual parameters out when the corresponding pixel arrives at input of MoG. Then, after finishing the processing, MoG block outputs foreground masks as the output stream and updated parameters as model data. Model data will be written back to a file after being compressed by the compression unit. In the following section, we will study the effect of applying different compression methods on MoG's model data.During the exploration, we assess the quality against the ground-truth (MoG with no compressed Gaussian parameters). We use MS-SSIM metric. MS-SSIM focuses on the structural similarity between two frames which is more similar to human perception[START_REF] Wang | Image quality assessment: from error visibility to structural similarity[END_REF]. MS-SSIM quantifies the quality as a value between 0 to 1 where a higher value means closer similarity and thus lower quality loss compared to ground-truth.

Figure 6 :

 6 Figure 6: Quality-Bandwidth trade-off in MSBSel compression scheme

Figure 7 :

 7 Figure 7: Visual structure of Gaussian parameters. Since JPEG has been customized for compressing images, we only limit the JPEG compression for parameter Mean. Parameter Mean keeps background mean values for pixels and it has a visual structure similar to an image. Fig. 7 illustrates the visual structure of all Gaussian parameters. On top from left to right, the original, background and foreground frames are shown. Below the frames, Fig. 7 also presents the images of all Gaussian parameters for three Gaussian components: Mean, Standard Deviation and Weight, from left to right. Fig. 8a shows the effect of JPEG-2000 compression on Mean parameter over the bandwidth demand for updating parameter Mean. Fig. 8b plots the total bandwidth saving (over all parameters), by compressing only parameter Mean. For this experiment, a sequence of 650 frames with resolution of 320x240 has been chosen as the input test set. Both figures show the effect of different JPEG compression ratios (2:1 -10:1). The JPEG-2000 is significantly reducing the bandwidth demand for updating the Mean parameter. For the best compression ratio of 0.1 (10:1), the bandwidth saving for updating parameter Mean is about 85%, indicating that the size of compressed Mean image is on

Figure 9 :

 9 Figure 9: Quality-Bandwidth trade-off when for simple and complex frame sequences

Figure 10 :Figure 11 :

 1011 Figure 10: Bandwidth saving and computation demand over different block sizes.

  and

					Bandwidth Saving vs. Image Block Size
		40%
	Average Bandwidth Saving	10% 20% 30%	QZIP LZ4 LZ4-HighComp. ZIP
			GZIP
			BZIP
		0%
		40x30	80x60	160x120	320x240	640x480	1024x768
					Image Block Size
				(a) Bandwidth saving

  • Quality-Bandwidth Trade-off (for MSBSel only and MSBSel+JPEG-2000): For having better quality, higher bandwidth is needed • Bandwidth-Compression Ratio (for MSBSel+JPEG-2000): By changing the configurable compression ratio in JPEG-2000, different bandwidth demands are achievable -Lossless Compression • Computation Demand-Block Size Trade-off (For all 5 lossless algorithms): Different block sizes lead to different computation demands, highest computation demand is when the block size is equal to the whole frame being compressed • Bandwidth Saving-Block Size Trade-off (For all 5 lossless algorithms): Different block sizes lead to different Bandwidth Saving, biggest saving in Bandwidth achieved when largest block size is used • Bandwidth Demand-Computation Demand Trade-off (For all 5 lossless algorithms): For having lower bandwidth demand or highest bandwidth saving, there is need for more computation • Bandwidth Demand-Computation Demand Trade-off for LZ4 algorithm in high-


Kasra Moazzemi
email: moazzemi.k@husky.neu.edu

Gunar Schirner
email: schirner@ece.neu.edu

Ran Hao
email: hao.r@husky.neu.edu

Nasibeh Teimouri
email: nteimouri@ece.neu.edu

Modeling and Analysis of SLDL-Captured NoC Abstractions

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Chip Multiprocessing (CMP) as one essential solution for parallel processing and high performance computing has evolved to exploit parallelism in the form of integrating multiple processor cores on a single chip which is known as System on Chip (SoC). To power and performance efficiently connect the cores, reusable interconnect architectures are required that provide scalable bandwidth and parallelism.

These requirements cannot be met by traditional interconnect architectures like single shared bus or even hierarchy of buses due to their poor scalability as they allow only one (or a few number of) sender-to-receiver communication(s) at a time [START_REF] Sgroi | Addressing the System-on-a-chip Interconnect Woes Through Communicationbased Design[END_REF]. Promising alternatives are Networks on Chip (NoCs). NoCs avoid the need for dedicated wires for each individual communication, and connect IP cores through an on-chip network. Several advantages compared to dedicated wires include delivering high-bandwidth, low-latency and low-power communication over a flexible and modular medium [START_REF] Owens | Research Challenges for On-Chip Interconnection Networks[END_REF] [START_REF] Dally | Route packets, not wires: on-chip interconnection networks[END_REF].

Different NoC design parameters (e.g. topology, communication mechanism, routing method and switching mode) impact a multi-dimensional trade-off space between latency, throughput, communication load, energy consumption, and silicon area. Therefore, early evaluation of NoC is in high demand [START_REF] Moraes | HERMES: An Infrastructure for Low Area Overhead Packet-switching Networks on Chip[END_REF]. Recent approaches on NoC emulation aim for accuracy. However, they could be too slow, especially when considering the tight time-to-market [START_REF] Foroutan | An analytical method for evaluating Network-on-Chip performance[END_REF].

System level modeling can relieve time to market pressures and the expense of NoC simulation/emulation tools with providing faster architecture exploration, performance evaluation, and functional validation [START_REF] Schirner | Abstract Communication Modeling: A Case Study Using the CAN Automotive Bus[END_REF]. Abstract modeling of an NoC poses the question of abstraction levels (the amount of detail to be retained in the model). Ultimately, this poses a trade-off between simulation speed and accuracy [START_REF]Quantitative Analysis of Transaction Level Models for the AMBA Bus[END_REF] as visualized in Fig. 1.

Accuracy

Speedup

Figure 1: Speed Accuracy Trade-off

A highly abstract NoC model abstracts away much of the underlying communication details, and in result yields a very fast but inaccurate simulation. Conversely, an accurate model would capture more of the communication principles, resulting in a slower but more accurate simulation. Although [START_REF] Lu | Accurately timed transaction level models for virtual prototyping at high abstraction level[END_REF] discusses about different abstraction levels, their precise definition and modeling abstraction rules are not clearly presented. Defining abstraction levels helps designers to select communication features to model given a desired speed/accuracy. This paper first identifies different NoC abstraction levels according to the visibility of implementation details and communication granularity. A most abstract model treats the whole NoC as one black box, only revealing input and output traffic. Conversely, the most detail level exposes how individual flits are handled at the micro-architecture level. This paper defines accuracy impact factors at each level, highlights contention points over shared resources within an NoC and identifies the required arbitration points.

Next, the paper proposes an abstract NoC model using Transaction Level Modeling (TLM). It realizes the structure of Hermes router model [START_REF] Moraes | HERMES: An Infrastructure for Low Area Overhead Packet-switching Networks on Chip[END_REF] with 5 bidirectional (both input/output) ports to the four neighboring IP cores and one port to the local IP core.The model implements XY routing and wormhole switching. The proposed TLM captures all the router features and arbitration events over its shared resources at cycle-level. It updates the system status at each cycle independent of how many arbitration events are notified during that cycle.

To evaluate the performance and accuracy of the proposed TLM versus an accurate model, this paper also introduces a more detailed model, a Bus Functional Model (BFM). The BFM follows the bus functional modeling principals [START_REF] Schirner | Abstract Communication Modeling: A Case Study Using the CAN Automotive Bus[END_REF] aiming to be as accurate as an RTL implementation. The BFM captures much more structural and microarchitectural detail and it updates the system status upon any arbitration event. This improves accuracy at the cost of simulation speed.Our TLM is 10 times faster than the BFM at the cost of 10% to 20% error.

The rest of this paper is organized as follows: Section 2 discusses related work in NoC modeling and analysis. Section 3 defines different abstraction levels for NoC modeling. Section 4 first presents the structure of modeled router, then proposes our TLM and BFM NoC abstract models. Following that, Section 5 validates the proposed BFM as accurate against an RTL implementation of NoC and then evaluates the proposed TLM versus BFM. Finally Section 6 concludes the paper.

Related Work

Exploring the design trade-offs of NoC metrics including bandwidth, power, performance and silicon area can be done at different levels of accuracy and details based on the design requirements. For instance, SW development needs fast simulation. Conversely, performance estimation demands a finer set of details and higher accuracy for proper validation [START_REF] Indrusiak | Fast and accurate transaction-level model of a wormhole network-on-chip with priority preemptive virtual channel arbitration[END_REF]. In general, work on evaluating NoC can be categorized in 3 groups: emulation/simulation frameworks, static analysis, and abstract modeling.

Emulation/Simulation Framework: Many NoC simulators and emulators have been developed; the emulation platform proposed by Dally et al. as a flexible emulation environment implemented on FPGA based on a complete mixed HW-SW NoC emulation framework, Xmulator [START_REF] Nayebi | XMulator: A Listener-Based Integrated Simulation Platform for Interconnection Networks[END_REF] as an event-driven simulator and Booksim [START_REF] Jiang | A detailed and flexible cycle-accurate Network-on-Chip simulator[END_REF] as a cycledriven simulator are a few instances of tools in this category. All instances impose high implementation cost, maintenance difficulty and long emulation/simulation time.

Some works [START_REF] Hosseinabady | SystemC architectural transaction level modelling for large NoCs[END_REF] and [START_REF] Viaud | An Efficient TLM/T Modeling and Simulation Environment Based on Conservative Parallel Discrete Event Principles[END_REF] aim to reduce the emulation/simulation time by changing the kernel scheduler, simulation/evaluation semantics by adding local clocks/schedulers. Nevertheless, their improvements are case-specific, for instance [START_REF] Hosseinabady | SystemC architectural transaction level modelling for large NoCs[END_REF] gains more as the size of NoC gets larger.

Static Analysis: Static analysis like [START_REF] Suboh | Analytical modeling and evaluation of network-on-chip architectures[END_REF] and [START_REF] Ogras | An Analytical Approach for Network-on-Chip Performance Analysis[END_REF]rapidly yields timing parameters such as router service time and packet arrival time. These methods have low accuracy as they abstract away dynamic behaviors influencing NoC performance and bandwidth.

Abstract Modeling: Abstract modeling might be placed in between two above categories. It abstracts away some implementation detail (such as bit-level communication details) and takes into account only the events occurring per transmission of coarser data granularity. The goal is to accelerate the NoC evaluation while maintaining some accuracy. The architectural model in [START_REF] Indrusiak | Fast and accurate transaction-level model of a wormhole network-on-chip with priority preemptive virtual channel arbitration[END_REF] is one example. It models the HERMES [START_REF] Moraes | HERMES: An Infrastructure for Low Area Overhead Packet-switching Networks on Chip[END_REF] router architecture as a bus and all cores/routers connected to it as individual modules. With keeping track of all routers' active flows in different FIFOs and prioritizing their requests based on the pre-defined priorities, all the competitions over the shared resources are captured. The drawback of this work compared to the proposed TLM is its evaluation for worst-cases; when all possible contentions over the shared resources happen. Similarly, [START_REF] Van Moll | Fast and accurate protocol specific bus modeling using TLM 2.0[END_REF] proposes an accurate abstract model for on-chip interconnects. It uses bus protocol specifications to identify a reduced set of timing points. Finding the set of optimal timing points is the drawback of this work compared to the proposed TLM.

NoC Abstraction Models

Conceptually, many abstraction levels are possible that may range from an extremely coarse grain model the treats the whole NoC as one black box, to a very fine-grained model that exposes micro architectural implementation details of all the NoC elements. Abstracting NoC can occur with different levels of details; from low covering details such as observing the whole NoC as a communication box to considering all microarchitectural implementation details of all NoC elements. When comparing abstraction levels, the following aspects should be considered:

Granularity of data defines the smallest unit of data transferred through the NoC.

Visibility defines the level of implementation details of NoC communication observable in the model. Arbitration points lists the shared resources for which contention is dynamically resolved. Timing accuracy outlines the resulting estimation accuracy; meaning that at which level of accuracy, an NoC model can estimate the timing behavior of a real NoC. Given the characteristics above, we propose five abstraction levels. Table 1 summarizes the models, and Fig. 2 illustrates the 3 most abstract models.

Network-Level Model: models the whole NoC as a black box and only exposes the local ports. This model abstracts away everything inside NoC including traffic paths and contentions over the shared resources. The model estimates network latency based on statistical information like average/worst case network latency per pre-defined size of traffic and the amount of traffic transferred through the network. Router-Level Model: realizes NoC as a set of routers connected to each other via physical channels. In this model, routers are modeled as black boxes which receive packets as input and sends output packets over a physical link to the next router. This model estimates the NoC performance/latency based on the number and size of packets as well as the length of path taken by each packet. It dynamically resolves contention on physical links. Transaction-Level Model: more details over the router-level model by modeling router internal modules, including input/output ports, cross-bar, routing management, virtual channel (VC) allocation and flow control management.

In this model, at the end of any transaction, the contentions (and arbitration events to resolve them) which change the system status are collected and the system status is updated. Based on [START_REF] Ghenassia | Transaction-Level Modeling with Systemc: Tlm Concepts and Applications for Embedded Systems[END_REF], a transaction is defined as injecting the header flit (first part of a packet) by initiator and receiving the last flit of the packet by the receiver. Pin-Level Model: implements all the internal wires/pins per router modules and updates the system status after any individual contention (and arbitration to resolve that) happening per transmission of each bit of the transaction. Micro-Architectural-Level Model: implements the Pin-Accurate model and all of it's router operations at gate level for final validation. This model is practically an RTL model, very close to the final implementation, most accurate but also the slowest.

From the network-level model to micro-architectural level model, communication and implementation details are added to the model, increasing accuracy at the cost of simulation speed. Table 1 summarizes the abstraction levels. Our router models are based on the HERMES router architecture [START_REF] Moraes | HERMES: An Infrastructure for Low Area Overhead Packet-switching Networks on Chip[END_REF] with slight changes. Fig. 3 outlines the router's internal structure with 4 important functional units: Input/Output Ports, Routing Management Unit (RMU), Flow Control Unit (FCU) and crossbar unit. RMU includes Routing Logic Unit (RLU) and central table to record the status of virtual channels (VCs) of the output ports. FCU for promulgating free ports to the neighboring output ports. Crossbar unit forwards the packets to the next router determined by the RMU.

Each router is connected to 4 neighboring routers through the 4 input/output ports. One local port connects the router to the local IP core. Each input port has a configurable (8bits in Hermes, 32bits in our model) size of VC-buffers to record the received data/control flits. A flit is the smallest part of a packet. There is no buffer in the output ports as the buffer in the next router's input port is used. For this, a credit-based flow control mechanism is employed to notify the sending side about the available space on the receiving side. This way, flit is only sent if there is space on the receiving side. The RLU (part of RMU) computes which output port to sent a packet to. The VC allocation unit selects which VC to use for a given output port. One of our changes over the Hermes architecture is supporting individual RLUs for each input port in order to avoid congestion inside the router. Similar to Hermes, the routing method is XY; approaching the destination always first horizontally, then vertically or vice versa. Routing decision is made per header flit which contains destination information and packet length. Flits are switched using the wormhole method.

Packet Transmission

Example a received flit is stored in the VC buffers of that input port. In case of a header flit, it's destination is forwarded to the RMU to determine the output port. After selecting the output port, the RLU consults RMU table to find an available VC on the output port.

After selecting output port and VC, the input port refers to FCU to check if there is enough room for receiving this flit in the next router. In our credit-based flow control, each VC has a credit and when the VC is used by a flit, its credit is decreased. When the flit leaves the input buffer of the destination router, a credit is sent back to the sending router, increasing the VC's credit count.

Assuming sufficient sending credit is available, the crossbar sends the flit from the input port to the output port (and subsequently sends a credit upstream). The remaining flits of this packet are then sent one by one consulting the FCU about receive buffer credits to the next router. Upon receiving the tail flit, the RMU de-allocates the output buffer and VC.

During packet transmission within a router, various shared resources are used for which accesses need to be arbitrated. Detecting and resolving/arbitrating the contentions impacts the accuracy.

Arbitration Points

One of the most important aspects impacting accuracy in modeling is detecting contentions over shared resources and resolving them. Shared resources are FCU, crossbar, and output ports. The way how access requests to these shared resources are collected and arbitrated affects the modeling accuracy. We identify one contention type for each resource (see also summary in Table 2):

1. Connection Establishment: if a router receives two header flits that target the same output port, their requests contend for the RMU. An arbiter is required to select one of requests. The selected request gets access to the RMU (central table of RMU), then starts connection and sends data. 2. Request Flow Control Grant: simultaneous flow control requests at the same FCU for different VCs create contention over FCU access. Concurrent requests are feasible, as they have already received the credit to send data. In order to guarantee that at one point of time, only one traverse is allowed to a specific output port, an arbiter is necessary to give flow control grant signal to one of the requests. We define this arbitration point as arbitration for same output accesses. 3. Crossbar Access: when more than one VCs at the same input port gets the flow control grant simultaneously, there is contention on the crossbar. In our design, to avoid this contention, we define an arbiter for crossbar access from the same input port. This arbiter grants crossbar access to only one of the requests.

NoC Abstract Models: TLM and BFM

This paper captures two abstract models of NoC; Transaction-Accurate Model (TLM) and Pin-Accurate Model (BFM) in the System-level Design Language (SLDL), SpecC [START_REF] Gerstlauer | System Design: A Practical Guide with SpecC[END_REF]. Both models take into account the arbitration points explained in Section 4.3 as well as the characteristics of Table 1. However, they differ in the way that requests to the shared resources are collected and arbitrated. The BFM gathers resource access requests based on sampling and driving of every single wire at each cycle. Conversely, the TLM gathers the access information at transaction. Consequently, the BFM updates the system status at any cycle, while the TLM updates at transaction boundaries. As the granularity of updating the system status affects the accuracy, TLM is less accurate than BFM. Both models implement the same arbitration policies. However, as the TLM makes a decision at a coarser granularity, it is more susceptible to the order in which access requests appear. Within the same time quantum, the TLM cannot distinguish between concurrent requests. As the execution order is not specified by the underlying discrete event simulation semantics, the effective arbitration policy for simultaneous (same quantum) becomes random.

Moreover, the BFM is driven by an explicit clock, while the TLM virtually times routers by using the instruction waitf or. In some sense the TLM can be considered time driven, while BFM is event-driven. Both models also differ in the number of threads (sc module in SystemC, or behavior in SpecC) used for simulation. The BFM employs active threads for each router module. Conversely, the TLM is mainly channel based (ie. is call driven) and only uses one behavior (or sc module) for each VC. For instance, assuming 4 VCs per physical link, the BFM has 41 simultaneous threads and the TLM only 20. With the lower number of active threads, the TLM can perform faster (avoiding context switches). Table 3 compares BFM and TLM.

Experimental Results

This section explores the proposed BFM and validates its accuracy and functionality with respect to the RTL implementation. It then compares the TLM versus the BFM based on speed and accuracy.

For evaluation of the models, we mainly use hot spot traffic [START_REF] Fulgham | Performance of Chaos and Oblivious Routers Under Nonuniform Traffic[END_REF]; some nodes in the network receive most of the traffic.

BFM Validation

System performance and throughput are two important metrics for analyzing NoC architectures. Average packet latency is a representative of system performance, and link utilization is a representative of throughput. Packet latency is the packet life-time defined as the difference between its start time label and its end time label.

Link utilization/load is the ratio of link busy time over the whole simulation time. Link busy time is defined as the total time when the link is busy carrying traffic.

In this part and for validation of the proposed BFM, we adopted 40%-hot spot traffic and defined packet size as 10 flits. 40%-hot spot traffic means that 40% of the nodes are the destinations of total traffic injected to the network. Each injector (hot node) injects 100 packets to the network. Fig. 4 shows the simulation results including link load, average packet latency and simulation time for hotspot traffic injected into the 8*8 mesh. The results are correlated with the results of VC extended HERMES router structure on FPGA [START_REF] Mello | Virtual Channels in Networks on Chip: Implementation and Evaluation on Hermes NoC[END_REF].

Fig. 4a shows link load for different numbers of VCs as the injection rate increases. At small injection rate, the link load increases linearly for all VCs. However, the link load starts to level off from a specific injection rate, around 10%, 15%, 20% and 30% respectively for 1 VC, 2 VCs, 4 VCs and 8 VCs. Based on [START_REF] Mello | Virtual Channels in Networks on Chip: Implementation and Evaluation on Hermes NoC[END_REF], this point is called saturation point. The saturation degree of network for multiple VCs in our model is higher than what is reported in [START_REF] Mello | Virtual Channels in Networks on Chip: Implementation and Evaluation on Hermes NoC[END_REF]. The reason lies in the different implementations of the network interfaces. In our work, we define multiple VCs for local connections as well, which means at the destination node, traffic from different ports can sink into the local PE without being blocked. With the improved mechanism, the network throughput for VCs of 8 can reach 100% under hotspot traffic. Fig. 4b shows the average latency as injection rate increases. Up to the saturation point, the average latency is constant for all VCs. With increasing the number of VCs, the average latency drops in a half when VCs goes from 1 to 2. Similar situation for 2 VCs to 4 VCs. However, the average packet latency for VCs of 4 and 8 are similar. The reason is that using 4 VCs has already eliminated most of packet blocking.

Fig. 4c shows the overall finish/transmission time as the injection rate increases. This time is when all the packets reach their destinations. Since more VCs leads to more traffic overlap on the fly, 8 VCs yields the shortest overall transmission time.

TLM Evaluation

This section evaluates the TLM compared to the BFM with respect to speedup and accuracy.

SpeedUp: depending on the amount of implementation details and number of context switches, the simulation time varies. For comparing the models, simulation speedup is reported. Simulation speedup of the model with higher level of abstraction (H) compared to the model with lower level of abstraction (L) is defined as 1.

Speedup H2L = Simu. T ime L / Simu. T ime H (1)
As the simulation time strongly depends on the number of context switches, the simulation speed is closely correlated with the network size and traffic intensity. Both network size and traffic intensity affect the the number of behaviors and context switches. Network size is the number of nodes in the network. Network intensity is defined as the number of transactions (number of packets) from sender nodes to the receiver nodes. With larger network or intense traffic simulation time increases.

To evaluate the effects of network size and traffic intensity, 40%-hot spot traffic is simulated with 4 VCs per physical link and 100% injection rate. Fig. 5a shows the simulation time for increasing network (mesh) size from 2*2 to 8*8. The TLM is 10x to 16x faster than the BFM. With larger networks, TLM achieves higher speedup as a result of abstracting away higher ratio of communication details. packet to 100 packets), TLM achieves an increasing speedup (from 14x to 50x) again as res ult of the more abstract simulation.

To measure the accuracy loss, we define accuracy error for each packet. As Equation (2) defines, this accuracy error has correlation with the difference between packet latency in the TLM and BFM. Packet latency is the difference between start time label and end time label of the packet.

Error = |P acketLatency L /P acketLatency H |/P acketLatency L (2)
As the TLM differs from the BFM in the effective arbitration policy (due to collection of requests and arbitration among them), measuring the accuracy loss in the TLM requires simulation scenarios with different amount of contentions (requests) over the shared resources. The amount of contentions over the shared resources is determined by the amount of traffic injected to the network. The more the injection rate, the higher the number of simultaneous requests for the same resources and higher contention and accuracy loss as a result. To demonstrate this, 40%-hot spot traffic is adopted into the TLM and BFM models of 6*6 NoC with 4 VCs per physical links and 100% injection rate. We simulate 100 transactions through the NoC and measure the transmission delay of packets in both models BFM and TLM. To aggregate the results, we report the average error, as well as the cumulative error for 50-percentile and 96-percentile as Fig. 6a. The 50-percentile (96-percentile) cumulative error indicates the maximal error experienced by 50% (96%) of transactions. As Fig. 6a represents, increasing the injection rate, increases the cumulative error probability. Increasing the injection rate from 0.1 to 0.2 increases the average error from 10% to 20%. At 0.1 injection rate 96% of packets observe less than 40% error, while 50% see less then 10% error. Increasing the injection rate to 0.6, makes 50% of packets experience up to 30% error. Increasing the injection of rate increases the contention over shared resources. One indicator is the congestion rate over physical links. Fig. 6b shows the cumulative error probability over increasing congestion. All three metrics are strongly related to congestion. And increase until congestion hits 50%. Then, 50% show at most 38% error, while the maximum error measured for 96% of packets reaches 100%. Conversely, at lower congestion rate, e.g. 5%, 96% of packets experience less than 20% error.

Conclusion

Modeling of NoCs is important for early exploration of NoC design alternatives. In this context, fast and accurate simulation is important. However, when abstracting NoC models, a trade-off between simulation speed and accuracy exists. This paper has identified NoC abstraction levels, differing in data granularity, visibility of internal structures and modeling of contention points. This paper has introduced two NoC models, an detailed Bus-Functional Model (BFM) which models and arbitrates at each clock cycle and a more abstract Transaction Level Model (TLM) that operates on coarser transactions. Both models have been captured in the SpecC SLDL. We have validated our BFM to sufficiently match the RTL implementation. The TLM simulates 10x to 50x faster than BFM at a cost of 10%-20% accuracy. Both speedup and accuracy loss increase with network size and traffic.

Figure 2 :

 2 Figure 2: NoC Modelling Granularities

Figure 3 :

 3 Figure 3: The Router Architecture in the Proposed NoC Abstract Models

Figure 4 :

 4 Figure 4: BFM Performance Validation (8x8 mesh, 40%-hot spot)

Figure 5 :

 5 Figure 5: Comparing simulation time of BFM and TLM (8*8 mesh, 40%-hot spot)

Figure 6 :

 6 Figure 6: Cumulative Probability of Accuracy Error

Table (

 (

		OP(S)
		OP(E)
		OP(W)
	Input Flit	OP(L)	Output Flit
		E)
		Table (W)
	Network Accurate	Table (L)
	Router Accurate
	Transaction Accurate

Table 1 :

 1 NoC Abstraction Overview

	Model	Visibiltiy Granularity Arbitration Point Time Unit
	Network-Accurate	-	Traffic	-	Loosely Time Estimated
	Router-Accurate	Channel Packet	Routers	Approximate Time Estimated
	Transaction-Accurate Channel Flit	Router Modules Cycle Estimated
	Pin-Accurate	Wire	Bit	Router Modules Cycle
	Micro-Arch	Wire	Bit	Router Modules Cycle
	4 Proposed NoC Models
	4.1 Router Architecture

Table 2 :

 2 Contention Events and Arbitration Points

	Arbitration point	location Resource Arbitration (BFM) Arbitration (TLM)
	Connection Establishment RMU RMU table FIFO	random
	Request Flow Control Grant FCU	output port FIFO	random
	Crossbar Access	IP	crossbar Round-robin	random

Table 3 :

 3 Comparing TLM and BFM

		BFM	TLM
	Communication Implementation Behavior	Channel
	Arbitration Policy	FIFO & Round-robin	Random
	Timing	Event driven (explicit clock) Time driven (waitf or)


Kasra Moazzemi
email: moazzemi.k@husky.neu.edu

Smit Patel
email: patel.smi@husky.neu.edu

Shen Feng

Gunar Schirner
email: schirner@ece.neu.edu

Rapid, High-Level Performance Estimation for DSE using Calibrated Weight Tables

Automated Design Space Exploration (DSE) is a critical part of system-level design. It relies on performance estimation to evaluate design alternatives. However, since a plethora of design alternatives need to be compared, the run-time of performance estimation itself may pose a bottleneck. In DSE, fastest performance estimation is of essence while some accuracy may be sacrificed. Fast estimation can be realised through capturing application demand, as well as Processing Element (PE) supply (later on called weight table) in a matrix each. Then, performance estimation (retargeting) is reduced to a matrix multiplication. However, defining the weight table from a data sheet is impracticle due to the multitude of (micro-) architecture aspects. This paper introduces a novel methodology, WeiCal, for automatically generating Weight Tables in the context of C source-level estimation using application profiling and Linear Programming (LP). LP solving is based on the measured performance of training benchmarks on an actual PE. We validated WeiCal using a synthetic processor and benchmark model, and also analyse the impact of non-observable features on estimation accuracy. We evaluate the efficiency using 49 benchmarks on 2 different processors with varying configurations (multiple memory configurations and software optimizations). On a 3.1 GHz i5-3450 Intel host, 25 million estimations / second can be obtained regardless of the application size and PE complexity. The accuracy is sufficient for early DSE with a 24% average error.

Introduction

Recent advances in technology have expanded the design options in terms of number and type of processors as well as their configurations such as interconnects and memory hierarchy. When this flexibility of design is coupled with the increasing pressure of time to market, performance exploration of the design space becomes exponentially difficult. Current approaches try to automate the Design Space Exploration (DSE). In any DSE, two questions need to be addressed. One is how to traverse the design space and other is how to assess the fitness of each design instance -all unique combinations of platforms and mappings. Millions of design options will be traversed before making a design decision. Evaluating the fitness of each design option falls on the time critical path of DSE and is at most importance here. Simulation based approaches can be highly accurate but too slow for DSE. New approaches are needed for rapid high-level performance estimation in context of DSE.

This paper revisits the retargetable profiling for rapid, early system-level design space exploration, introduced in [START_REF] Cai | Retargetable Profiling for Rapid, Early System-level Design Space Exploration[END_REF] and improves upon it. The retargatable profiler [START_REF] Cai | Retargetable Profiling for Rapid, Early System-level Design Space Exploration[END_REF] uses a weight table, which is a matrix of Processing Elements (PE) performance cost (cycles) of each high-level operation for all data types. One of the main challenges of retargetable profiling is that the weight tables need to be manually defined. The accuracy of weight table impacts the accuracy of final estimation. Due to manual extraction of these weight tables from the data sheet, this process is time consuming and error prone. Moreover, because of the high-level abstraction, only a few features of the processor are observable (can be quantified). For example, C statements do not reveal from where an operand needs to be fetched from within the memory hierarchy. Therefore, the cycles captured in the weight tables have to statistically include these non-observable characteristics such as memory accesses and pipeline stalls. These elements which can affect the performance but are not observed during execution make it very difficult to manually populate the weight table. In this paper, we present a methodology and a framework Weight Calibration (WeiCal) to automatically populate more realistic weight tables paving the way to efficient DSE.

The WeiCal framework consists of Calibration and Retargeting. A set of training benchmarks are profiled along-with the actual execution of those benchmarks on the target PE in calibration phase, generating a Linear Program (LP). This is fed to an LP Solver which defines the weight table of the particular PE, implicitly considering the vast number of architectural and micro architectural features. To estimate the performance of a target application, in the retargeting phase, it is profiled once to extract computational demand. Then, performance is estimated purely through a static approach by a simple matrix multiplication of the PE weight table and the application's computational demand. With this, multiple iterations of the retargeting step can rapidly estimate the performance of different target processors. The advantage of this method is that the application is simulated only once (for profiling), avoiding long repetitive simulations. In addition, due to fast computation in retargeting stage, this approach is particularly suitable for rapid comparisons in early DSE.

We validate WeiCal using a synthetic processor and benchmark model, and also analyse the limitations of this approach. We evaluate the efficiency of the proposed methodology using 49 benchmarks on 2 different processors with varying configurations (multiple memory configurations and software optimizations). On a 3.1 GHz i5-3450 Intel host, 25 million estimations / second can be obtained regardless of the application size and PE complexity. The accuracy is sufficient for early DSE with a 24% average error.

The rest of this paper is organised as follows: Section 2 presents an overview of work related to this approach. Section 3 introduces retargetable profiling. Section 4 presents WeiCal and 5 presents implementation. Section 6 presents a synthetic model to validate the approach. Section 7 shows experimental results and Section 8 concludes the paper.

Related Work

Many estimation methods have been proposed trying to solve different challenges in estimation such as accuracy, speed and being application specific. They generally estimate based on one of three abstraction levels: : source-level (high-level), intermediate-level and binary-level (low-level). At high-level, fewer details are taken into account. It is faster and retargetable but less accurate in terms of absolute performance numbers. On the other side, low-level estimation benefits from more target architecture knowledge increasing accuracy at cost of simulation speed. While low-level may produce cycle approximate estimations for detailed analysis, high-level estimation is more suitable for DSE due to estimation speed.

Various high-level estimation techniques have been proposed. The authors of [START_REF] Lattuada | Performance modeling of embedded applications with zero architectural knowledge[END_REF] propose an approach which has limitations due to compiler optimizations. Wang et al. [START_REF] Wang | An efficient approach for system-level timing simulation of compiler-optimized embedded software[END_REF] present an approach which takes compiler optimizations into account. However, both these approaches rely on simulation for estimation. The authors of [START_REF] Lin | Compiler-assisted technique for rapid performance estimation of FPGA-based processors[END_REF] propose a compiler-assisted technique to rapidly estimate without simulation. However, this approach is developed for the FPGA based processors. Oyamada et al. [START_REF] Oyamada | Software Performance Estimation in MPSoC Design[END_REF] present an integrated approach for system design and performance analysis. An analytic approach based on neural networks is used for high-level software performance estimation. This approach takes about 17 seconds to estimate the performance of an MPEG4 encoder application. A hybrid simulation method is introduced in [START_REF] Gao | Multiprocessor performance estimation using hybrid simulation[END_REF] which also uses a cache simulator to measure memory access delay. [START_REF] Stattelmann | Fast and accurate source-level simulation of software timing considering complex code optimizations[END_REF] presents a complementary method for increasing the accuracy of approaches that are annotating timing information into source code by mapping binary representation to source level. This approach requires the source code and the binary-level CFG. In [START_REF] Hwang And Abdi | Cycle-approximate Retargetable Performance Estimation at the Transaction Level. Design, Automation and Test in Europe[END_REF], an estimation approach is proposed for transaction level. One drawback of this work is that the mapping between the C processes to PEs should be determined before using this estimation approach. These approaches are suitable for estimating the performance of a PE, but efficient design space exploration requires faster retargetability.

Javaid et al. [START_REF] Javaid | Rapid runtime estimation methods for pipelined MPSoCs[END_REF] propose two estimation mechanisms whose goal is to minimise the estimation time. Though the approach is retargetable for pipelined MPSoCs, the performance estimation of individual component of design space is yet not retargetable. Mohanty et al. [START_REF] Mohanty | Rapid system-level performance evaluation and optimization for application mapping onto SoC architectures[END_REF] present a mechanism for DSE using interpretive simulation which requires specific inputs to the proposed model.

We base our work on [START_REF] Cai | Retargetable Profiling for Rapid, Early System-level Design Space Exploration[END_REF] for DSE as it is retargetable and does not involve simulating the target application across the design space. However, the estimation accuracy of this approach is largely dependent on the weight table entries of PEs in the design space.

Retargetable Profiling

Retargetable profiling [START_REF] Cai | Retargetable Profiling for Rapid, Early System-level Design Space Exploration[END_REF] is a high-level estimation technique, which is divided into two stages -Profiling and Retargeting.

In the profiling stage, the system specification is instrumented and simulated to gather basic block execution counts. Static analysis then computes the number of operations executed (distinguished by type) for each data-type executed and stored in the form of specification characteristic table. This specification characteristic table has the format same as weight table of a PE. Note, the profiling stage is done only once per application.

In the Retargeting stage, the designer decides the mapping of behaviour to a PE. Performance of executing the behavior on the selected PE is estimated by multiplying specification characteristics (obtained from profiling) with delay values stored in the weight table of that PE. The total performance (E) of that PE is computed through a matrix multiplication and sum.

E = OpT ype DataT ype (F OpT ype.DataT ype × W OpT ype.DataT ype ) (1)
where W OpT ype.DataT ype is the weight (i.e. clock cycles) and F OpT ype.DataT ype is the occurrence frequency of each operation type OpT ype of data-type DataT ype.

Since retargeting consists of a pure static approach, it avoids the time-consuming steps of simulation and profiling.

With its extremely fast estimation speed, retargetable profiling is very suitable for DSE. However, it requires a tedious manual step of extracting the weight table information (execution delay for each operation and datatype combination) from the data sheet of each PE. Considering that the IP vendors have their unique way of representing this information, data collection can be timeconsuming. Furthermore, dedicating only one table for each processor limits the designer to one configuration in terms of compiler optimizations and hardware configurations. This limitation makes the design space too simplistic. Moreover, some affecting elements are unknown, such as details of pipeline and data forwarding, because the vendors often do not release this information. This poses many challenges to manually define weight tables. This paper, introduces a framework for automatically generating the weight tables by calibration.

Weight Calibration (WeiCal)

This section proposes a technique for calibrating PE weight tables. It automatically populates the weight tables using a training set of benchmarks and a Linear Programming Formulation (LPF). This methodology expands flexibility of the retargetable profiling approach [START_REF] Cai | Retargetable Profiling for Rapid, Early System-level Design Space Exploration[END_REF], and can increase the accuracy by implicitly considering more architectural features.

An Overview of the Framework

As shown in Figure 1, WeiCal generates weight tables for PEs according to a set of training benchmarks. Every benchmark is captured in SpecC language (based on ANSI-C) and then profiled with SCProf profiler [START_REF] Cai | Retargetable Profiling for Rapid, Early System-level Design Space Exploration[END_REF] to determine the application computation demand. It includes the frequency of all operation types for each data type for the whole application. Each benchmark is also executed on a real processor (Processing Element (PE)) to obtain accurate benchmark execution cycles. An LP formulation is constructed using the benchmark characteristics and measured execution cycles. Solving this linear system yields the weight table for the PE.

Linear Programming Formulation (LPF)

This section describes the LPF to obtain weight tables. For each benchmark i on a particular PE, (B i ) specifies the measured execution time (cycles). D ij denotes the computational demand of benchmark i as determined by profiler. For ease of explanation, we fold every combination of operation-type and data-type into one index j. W j denotes the weight of one operation and datatype combination. An equation is generated for each benchmark which includes the weights of each operation-data-type combination, occurrence frequency of each combination and total execution time. The number of equations would be equal to the number of benchmarks available. The weights in each equations are the unknowns, which will be solved by LPF. However, as not all factors impacting the performance can be measured, the linear equation system cannot be accurately solved. To allow for some error in the estimation of each benchmark, we introduce a Calibration Fudge factor (CF). Finding the weights with the overall least absolute error (CF) will yield the most accurate estimation. The LPF is as follows:

Minimise:

Σ i |CF(i)| Subject to: Benchmark1 : D11.W1 + D12.W2 + ... + D1M .WM + CF1 = (B1) Benchmark2 : D21.W1 + D22.W2 + ... + D2M .WM + CF2 = (B2)
...

BenchmarkN : DN1.W1 + DN2.W2 + ... + DNM .WM + CFN = (BN )
where N is the number of benchmarks and M is the number of operation type and data-type combinations. Each benchmark is represented by one equation. Adding benchmarks will increase information for the LP Solver to find the weights of that PE, to then produce a more realistic weight table leading to a better future estimation.

Implementation

This section presents the benchmarks, tools, PEs and metrics that are used for evaluating the approach.

Benchmarks used in the framework play an important role in estimation process. Balance in distribution of these benchmarks allows more accurate estimation for future applications. A major effort has been devoted to gather a suitable set of benchmarks that can cover most of operations, data types and coding structures. Table 1 shows the benchmarks. In Table 1, Randomly Gen-

Source

Names of Benchmarks MiBench [START_REF] Guthaus | MiBench: A Free, Commercially Representative Embedded Benchmark Suite[END_REF] & AES whetstone bcnt blit bubblesort cnt crc crc2 edn fft1 fir2 DSP-Stone [START_REF] Zivojnovic | DSPstone: A DSP-Oriented Benchmarking Methodology[END_REF] gamma hanoi heapsort linpack lms lms2 ludcmp matmult matrix basicmath ndes nsichneu peakSpeed1 prime queens v42 wavelt Randomly frand1 frand10 frand12 frand13 frand16 frand17 frand18 Generated frand19 frand2 frand20 frand3 frand4 frand6 frand8 frand9 rand3 rand5 rand6 rand7 rand8 rand9 Synthetic synadddouble synaddfloat synaddlonglongint syndivdouble syndivint syndivlonglongint synmindouble synminfloat synminint synmulfloat synmulint synmullonglongint synmuldouble synaddint synminlonglongint syndivfloat WCET adpcm crc2 edn fft1 fir2 lms ndes nsichneu qurt erated benchmarks have been generated using the modified Randprog tool [START_REF] Eide | Volatiles Are Miscompiled, and What to Do about It[END_REF]. Synthetic benchmarks predominately focus on a operation and data-type combination. They are only used for calibration only. The WCET benchmarks are a subset of those presented in [START_REF] Gustafsson | The Malardalen WCET Benchmarks -Past, Present and Future[END_REF]. We used the SCProf [START_REF] Cai | Retargetable Profiling for Rapid, Early System-level Design Space Exploration[END_REF] profiler to extract application demand and gcc to compile the benchmarks for real hardware. We used the open source SCIP solver [START_REF] Achterberg | Mathematical Programming Computation[END_REF] to solve LPF. We have applied WeiCal to two different processors (Black-fin527 [START_REF] Devices | Blackfin Embedded Processor[END_REF] and ARM9 [START_REF]C2440A[END_REF]), with various hardware configurations (SRAM and SDRAM with Blackfin527 [START_REF] Devices | Blackfin Embedded Processor[END_REF]) and compiler optimizations (O0, O1, O2, O3 with ARM9 [START_REF]C2440A[END_REF]).

As metrics, we mostly use absolute error, comparing real execution cycles with estimated cycles. However, absolute accuracy may not always be required. During DSE, different design alternatives are compared. In this setting, the correctness of a relative comparison is sufficient. Fidelity quantifies the correctness of a relative comparison.

The dimensions of the weight table and specification characteristic table are defined by the number of possible operations (number of rows) and datatypes (number of columns). The SCProf profiler distinguishes 55 operations and 16 datatypes. This leads to 880 different pairs of operations over datatypes. In order to estimate 880 weights (execution delays), the LP formulation needs at least 880 training benchmarks. It is challenging to collect such a large number of suitable benchmarks. In addition, it would lengthen the LP solver run-time. To reduce the number of required benchmarks, we reduce the dimensionality of the weight table by grouping similar operations and datatypes based on architectural assumptions. Table 2 summarizes our assumptions. Overall, we group all operations into 12 different operation groups and all datatypes into 4 datatype groups. This dramatically reduces the of combinations from 880 down to 48 combinations of operations and datatypes.

Validation through Synthetic Model

Any estimation approach is limited by the number of observable features (profiling restrictions), and by the complete availability of processor performance information (limited micro-architectural knowledge). To initially validate and optimise our approach under known conditions, we employ a synthetic model. We designed a statistical model which produces synthetic PEs and synthetic benchmarks to be used in WeiCal. Using synthetic model increases visibility over real measurements and processors. Each processor is modelled by a set of elements that contribute to delay in execution (such as execution of an operation, cache hit and cache miss). To mimic the effect of partial observability by the profiler, we declare some of these effects as observable, while other effects as non-observable. The number of training benchmarks and non-observable elements are varied to study their impact on the estimation accuracy. In order to realise the non-observable elements, their effect was deliberately included when calculating the measured execution time. However, the occurrence of nonobservable elements in benchmarks is hidden from the profiler. In result, the profiler counts only the observable elements, while the timing measurement includes delay (cycles) due to observable as well as non-observable elements. The LPF will attribute the effects of non-observable elements to the observable elements. As such, the number of cycles will increase for each observable feature. This is similar to other models which for example fold memory access delay statistically into operations. Processor P is modelled as

P = [W k ][W u ] (2)
where [W k ] is the set of delays for known elements and [W u ] is the set of delays of unknown elements. The particular values for [W k ] and [W u ] are randomly chosen (linear distribution) during the generation of a processor model. Similarly, a synthetic benchmark is defined as recurrence of elements known and unknown to the Profiler.

B = [R k ][R u ] (3)
where [R k ] is the set of recurrence for known elements and [R u ] is the set recurrence of unknown elements. The particular values for [R k ] and [R u ] are randomly chosen (linear distributed) during the generation of a benchmark. The delay of a specific synthetic benchmark i on a particular synthetic PE j is defined as (Delay

) ij = [R k ] i [W k ] j + [R u ] i [W u ] j (4)
Figure 2 shows the effect of non-observable elements evaluated by changing the ratio of observable elements to non-observable elements in the synthetic model. The total number of elements was constant (60), while varying the nonobservable elements as 2%, 25%, 40% and 60%. The non-observable elements was set to contribute 15% of the total computation demand.

In the upper left graph of Figure 2, the mean estimation error quickly converges to 2% when the number of training benchmarks reaches 60. With 25% non-observable elements, the mean estimation error stays at 12% with more than 60 training benchmarks (upper right). When non-observable elements increase to 40% or even 60% , both the average and absolute estimation error are high. The estimation error is no longer improved with more than 60 training benchmarks.

It indicates that the number of training benchmarks need to be necessarily larger than the number of elements in order to converge the estimation error. However, even a large number of training benchmarks does not improve the accuracy of the weight table and corresponding estimation when the non-observable elements are more than 40%. At least 50 training benchmarks are required for the estimation error to converge. The number of training benchmarks should be greater than the number of weights in the weight table for correct estimations.

The synthetic model allowed us to evaluate the effect of the non-observable elements and training benchmarks on the estimation error. The estimation accuracy improves with fewer non-observable elements. It is impossible to achieve a meaningful estimation with non-observable elements over 40% of all (observable and non-observable) architectural elements. Furthermore, the estimation error converges when the training benchmarks is slightly more than the desired observable elements. Adding more training benchmarks does not further improve the accuracy largely. Fig. 2. Effect of number of benchmarks on average error

Median

Experimental Results

The efficiency of our approach affects the high-level design decisions. On one hand, accuracy is desired to correctly guide the DSE. On the other hand, performance estimation should be fastest to evaluate many design combinations. Accuracy is evaluated is terms of absolute error and fidelity. In order to measure estimation error, we excluded one benchmark from the training benchmarks and used it as a target application to determine estimation accuracy. The procedure was repeated through all the real benchmarks. Real and synthetic benchmarks were used for calibrating the weight tables. However, only the real benchmarks were used as test applications as they better reflect the characteristics of an actual workload. The results are aggregated in Figure 3.

Figure 3 shows the median, quartiles, minimum and maximum of the estimation errors among all benchmarks across all PEs. The box plot shows these static quantities, while the violin plots show the distribution of estimation error across the benchmarks. Figure 3 also shows the effect of compiler optimizations and hardware configurations on the estimation error. The majority of benchmarks have an estimation error close to median (-6%) for Blackfin with SRAM. Moving from SRAM to SDRAM deteriorates the median to -30%. Most accurate results are achieved with low optimization. The ARM9 with O0 has the median at -11% with most of the benchmarks having an estimation error close to median. As the optimization increases, the association of source code with the execution time reduces. This is due to the weak correlation between source-level C code and binary at higher optimization levels. With an increased optimization to O1 for Fig. 3. Estimation Error on Real Platforms ARM9, the median is at -57%. WeiCal is able to distinguish between various software and hardware configurations. Some applications do not perform well in this approach in terms of the estimation accuracy. This is the cost being paid for estimating at the highest level of abstraction. In some configurations, WeiCal has a higher error than what was reported in [START_REF] Cai | Retargetable Profiling for Rapid, Early System-level Design Space Exploration[END_REF] as we are now using more complex processors, memory hierarchies and compiler optimizations.

In early DSE, fidelity (i.e. relative comparison) is sufficient and absolute accuracy is less important. In order to analyse fidelity, we describe fidelity matrix, which shows the fidelity between all the possible pairs of PEs from the design space. Table 3 presents the fidelity matrix. To further analyse fidelity, we plot also fidelity over the measured performance gap between the investigated PE configurations. Fidelity depends on closeness between real performance of PEs being compared. Table 3 shows that performance estimation using calibrative weight tables has high fidelity with average fidelity being 82%. Fidelity increases when performance gap between the compared PEs is larger. The estimated comparison of ARM9 O0 with its higher optimization counterparts is correct in more than 94% of the cases.

In addition to accuracy, the value of estimation methodology also depends on the time it takes for making an estimation. A separate aspect is the duration for generating a weight table (ie. performance of WeiCal). The weight table is determined only once in the lifetime of a PE and is less important. Hence, calibration takes place only once. We have automated executing benchmarks on target PEs and measuring execution duration (clock cycles). The average time it takes to load each benchmark is 2.5 seconds. The LPF took 0.6 seconds to generate the weight table for 48 given equations (48 benchmarks). The calibration phase took nearly 120 seconds in addition to the actual execution time of all benchmarks on the hardware.

Conversely to calibration, the estimation in retargeting to different PE configurations occurs very frequently during DSE. Thus, its performance is highly critical. Estimation is merely a matrix multiplication of the PE weight table and application profile table. As the dimensions of weight table and application profile table are fixed, the estimation time is independent of the application size and PE complexity. On a single core of 3.1 GHz i5-3450 Intel host, 25 million estimations / second can be obtained regardless of application size and PE complexity. Additionally, as the estimation is only a matrix multiplication, it's parallelization has been studied a lot. The average error of 24% is acceptable for early DSE where fidelity and high speed of estimation are more prominent factors.

Conclusion

Rapid estimation with sufficient fidelity is essential for DSE. In this context, retargetable source-level profiling [START_REF] Cai | Retargetable Profiling for Rapid, Early System-level Design Space Exploration[END_REF] is a promising approach. It profiles a specification once to determine the specification computation demand. Then, estimating the application's execution time is as simple as a matrix multiplication of the specification computational demand and weight table capturing the PE's computation supply. However, this approach heavily relies on the quality and availability of weight tables.

The work presented in this paper proposes a calibration-based framework to automatically determine a processor's weight table(s). It avoids the manual and error-prone process of manual capturing processor characteristics (execution time). In particular, it mitigates the challenge of limited visibility of the sourcelevel profiling (i.e. C statements) and the associated challenge of attributing non-visible characteristics into the accounted operations.

We devised a synthetic model in order to validate the approach and analyse the bounds. We measured efficiency of the WeiCal using 49 benchmarks (mainly MiBench and DSP Stone) on ARM9 and Blackfin BF527 processors and considered memory configurations (SRAM and SDRAM) and software optimizations (O0, O1, O2 and O3). With the weight table approach 25 million estimations / second can be performed on a single core of 3.1 GHz i5-3450 Intel host. The average estimation error was 24%. However, the approach offers higher fidelity especially with larger performance gap between (e.g. above 94% fidelity for comparing ARM0 at O0 with other optimizations). The high estimation speed with good fidelity makes this methodology an ideal cornerstone for an automated DSE.

Fig. 1 .

 1 Fig. 1. Framework Flow

Table 1 .

 1 List and categories of benchmarks

Table 2 .

 2 Grouping of operations and data types for dimensionality reduction

	Groups	Pristine entries in original weight table
	constant	constant
	array access	array access, content of
	function call	function call, return
	post increment	post increment, pre increment, post decrement, pre decrement
	not	bitwise not, logical not
	multiply	multiply, multiply/assignment
	divide	divide, modulo, divide/assignment, modulo/assignment
	add	add, subtract, add/assignment, subtract/assignment
	branch	if, if else, for, while, do while, default, switch, case, break, continue
	shift left	shift right, shift left
	equal	all compare operations
	or	bitwise or, logical or, exclusive or, and, logical-and
	assignment	all possible assignment operations
	int	unsigned long int, unsigned char, char, unsigned short, pointer, bool
		short, unsigned int, long int, unsigned long
	long long int	long long int, unsigned long long int
	float	float, unsigned float
	double	double, long double, unsigned double

Table 3 .

 3 Fidelity Matrix

		BF527 SRAM BF527 SDRAM ARM9 O0 ARM9 O1 ARM9 O2 ARM9 O3
	BF527 SRAM	100%	90%	89%	76%	80%	80%
	BF527 SDRAM	-	100%	76%	90%	93%	92%
	ARM9 O0	-	-	100%	94%	96%	100%
	ARM9 O1	-	-	-	100%	57%	61%
	ARM9 O2	-	-	-	-	100%	55%
	ARM9 O3	-	-	-	-	-	100%