Pierre Greisen

Michael Schaffner

Danny Luu

Val Mikos

Simon Heinzle

Frank K Gürkaynak

Aljoscha Smolic

Michael Schaner

Spatially-Varying Image Warping: Evaluations and VLSI Implementations

Keywords: image-based rendering, EWA splatting, bicubic resampling, video processing, anti-aliasing, interpolation quality, complexity evaluation, caching, VLSI

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

Introduction

With the steadily increasing frame rates and resolutions, real-time video processing and graphics processing is becoming predominant in terms of computational requirements in mobile devices. Many application-specic hardware cores for video processing are currently being integrated onto mobile system-on-chips (SoCs) (e.g., NVIDIA Tegra). One upcoming application for mobile devices is video content adaptation: while a growing amount of content is watched on an increasing number of dierent mobile platforms, most content is captured with one acquisition system at xed parameters. Examples for content adaption algorithms are content-aware video resizing (video retargeting) [START_REF] Krähenbühl | A system for retargeting of streaming video[END_REF], non-linear stereoscopic 3D (S3D) adaption [START_REF] Lang | Nonlinear disparity mapping for stereoscopic 3D[END_REF], 2D to S3D conversion and S3D to multiview generation [START_REF] Do | Immersive visual communicatio n[END_REF][START_REF] Farre | Automatic content creation for multiview autostereoscopic displays using image domain warping[END_REF][START_REF] Tanimoto | Free-viewpoint tv[END_REF]. Other content transformation applications are camera alignment for S3D video and panoramic shots. As a rst step, any display adaptation algorithm determines an image warping function that is dependent on the display characteristics. The input frames are then transformed to the output frames according to the given warping function using a view rendering algorithm based on spatially-varying warping. The generation of the warping function is application-specic, and can be separated from the view rendering. For instance in video retargeting, the warping function retains the aspect ratio of salient (i.e., visually important) parts of the image, while the image distortion is hidden in visually less important regions. In S3D to multi-view conversion, the warping function is derived from the 3D structure of the scene (obtained from a disparity estimation step) to generate in-between views.

Various view synthesis and image rendering architectures have been proposed in prior work. However, the majority of these architectures have been optimized for one particular rendering application, such as depth-image based rendering (DIBR) [START_REF] Chang | A 94fps view synthesis engine for HD1080p video[END_REF][START_REF] Horng | VLSI architecture for real-time HD 1080p view synthesis engine[END_REF], stereo rectication [START_REF] Greisen | An FPGA-based processing pipeline for high-denition stereo video[END_REF], or non-linear lens correction [START_REF] Asari | Design of an ecient vlsi architecture for non-linear spatial warping of wide-angle camera images[END_REF][START_REF] Oh | Fpga-based fast image warping with data-parallelization schemes[END_REF]. In contrast, we consider warping with general transformations that can be used for global per-frame transformations such as (wide-angle) lens undistortion, but also for spatially varying per-pixel transformations such as in video retargeting. Due to the spatially-varying nature of the transformation and the high resolutions of video footage in current applications, special care has to be taken in algorithm and architecture design. That is, aliasing needs to be avoided, high-quality interpolation should be guaranteed, and high computational and memory bandwidth requirements need to be addressed.

In this paper, we address hardware eciency and VLSI architectures of nonlinear warping for view synthesis applications. It is an extended version of our previous work [START_REF] Greisen | A generaltransformation EWA view rendering engine for 1080p video in 130 nm CMOS[END_REF][START_REF] Greisen | Analysis and vlsi implementation of ewa rendering for real-time hd video applications[END_REF]: next to the elliptical weighted average (EWA) rendering system presented in [START_REF] Greisen | A generaltransformation EWA view rendering engine for 1080p video in 130 nm CMOS[END_REF][START_REF] Greisen | Analysis and vlsi implementation of ewa rendering for real-time hd video applications[END_REF] we present non-linear image warping through bicubic interpolation and adaptive super-sampling and assess image quality and hardware requirements by comparing an extended set of non-linear warping strategies. An important hardware consideration is thereby the memory bandwidth requirements and the corresponding cache simulations and VLSI designs. Finally, using the obtained ASIC implementation results, we provide a comparison of dierent warping techniques in terms of VLSI performance.

Non-linear Image Warping Non-linear image warping is the process of geometrically transforming an image with a general image transformation (warping) function. In the simplest case, the image warping function can be represented as a global per-image transformation such as a rotation or translation of all the pixel values. Such transformations are usually represented by simple, per-image arithmetic operations of the input pixel locations. Stereo rectication is a practical application example: two non-aligned camera images are rectied in order to eliminate any vertical osets between the cameras, and a 3-by-3 matrix with 8 degrees of freedom is enough to specify the full image transformation. While our setup is able to perform global per-image transformations, its strength lies in the ability to realize locally-adaptive non-linear deformation of

Spatially-adaptive aspect ratio retargeting

Linear scaling Initial Image Fig. 1. Example of transformations possible with our non-linear image warping setup. In addition to global per-frame transformations such as rotations or linear scaling (right image) our system also allows arbitrary non-linear transformations (middle image). Such transformations are essential for spatially-adaptive retargeting applications. Image credits: the initial image (left) is in the public domain, the middle image is generated with the framework from [START_REF] Krähenbühl | A system for retargeting of streaming video[END_REF] and the right image is a linear scaled version of the initial image. the input video, which is required in modern video applications such as contentaware video retargeting. Our warping function can be specied by a per-pixel mapping function: any pixel in the source image is assigned its own destination pixel position in the target image. Figure 1 shows an example of transformations that are possible with the system presented in this work.

2.1

Warping Basics

In the following we briey summarize the image resampling process, for a thorough derivation we refer to literature (e.g. [START_REF] Szeliski | High-quality multi-pass image resampling[END_REF][START_REF] Wolberg | Digital image warping[END_REF][START_REF] Zwicker | EWA splatting[END_REF]). Consider an input image with pixel values w k , where k is the linearized image coordinate and u k the corresponding 2D coordinate in source (image) space. Each (non-integer) source coordinate u is transformed via mapping m to a target coordinate

x x = m(u) (1)
Further, let f i () be a continuous source space interpolation lter and f a () a continuous target space anti-aliasing lter. The general mapping function m then transforms an input image into an output image f out according to

f out (x) = k w k f i (m -1 (x) -u k ) * f a (x) = R 2 k w k f i (m -1 (τ ) -u k )h(x -τ )dτ . (2)
The interpolation and anti-aliasing lter are crucial for obtaining good image quality in the resampling process, and omitting them can lead to aliasing or holes in the output image, especially for spatially-varying transformations. The nal output image is obtained by evaluating f out on the desired integer grid positions.

In practice, the general mapping function m(u) is linearly approximated with a rst-order Taylor expansion around an integer grid position u k

x = m(u) ≈ m(u k ) + J k • (u -u k ), (3)
where J k is the 2 × 2 Jacobian matrix of m at position u k . Also, the resampling equation ( 2) can be evaluated in two ways. The so-called backward mapping approach steps through the output pixel positions x h and looks for the corresponding pixels in the input image. The forward mapping approach steps through the input grid positions u k and calculates its contributions to the target pixels. In the following, we introduce practical backward and forward mapping techniques for non-linear warping.

Forward Mapping: EWA Splatting

An ecient forward mapping approach is elliptical weighted average (EWA) splatting [START_REF] Greisen | Analysis and vlsi implementation of ewa rendering for real-time hd video applications[END_REF]. In the EWA framework, 2D Gaussian lters are used for both interpolation and anti-aliasing lters with covariance matrices V {i,a} = σ 2 {i,a} I 2 , where I 2 is a 2-by-2 identity matrix. Two main advantages of Gaussian lters make the EWA framework very eective: rst, a Gaussian lter remains Gaussian under linear transformations. Second, the convolution of two Gaussian lters results in another Gaussian.

Consider an input image with pixel values (intensities or RGB components) w k , where k is the linearized 2D image coordinate corresponding to the 2D position vector u k and an Taylor-approximated mapping m(u k ) + J k (u -u k ). The complete EWA resampling process is then summarized as follows. First, the per-pixel covariance matrix is calculated from the warping grid Jacobian J k and covariance matrices V {a,i}

C k = J k V i J T k + V a . (4)
The technique from [START_REF] Greisen | Analysis and vlsi implementation of ewa rendering for real-time hd video applications[END_REF] further adapts the resulting co-variance matrix C k on a per-pixel level and thereby optimizes the inherent blur-aliasing trade-o of Gaussian lters (see [START_REF] Greisen | Analysis and vlsi implementation of ewa rendering for real-time hd video applications[END_REF] for details). Next, for each input pixel k with position u k and value w k , we accumulate its contributions in the target image v h on target grid positions x h with linear index h

v h ← w k |J k | 2π |C k | e -0.5(x h -m(u k ) T C -1 k (x h -m(u k )) . (5)
The '←' symbol denotes an update operation (accumulation). Due to nonidealities, a post-normalization step is necessary: v h /ρ h , where ρ h are the accumulated weights

ρ h ← |J k | 2π |C k | e -0.5(x h -m(u k ) T C -1 k (x h -m(u k )) . (6)
In theory, x h is the complete target image grid; in practice, because of the fast decay of the Gaussian kernel, the range of x h can be conned by a rectangular bounding box around the transformed center of the Gaussian m(u k ) [START_REF] Greisen | Analysis and vlsi implementation of ewa rendering for real-time hd video applications[END_REF]

m(u k ) + ± C k (1, 1) ± C k (2, 2) . ( 7
)

Backward Mapping

Backward mapping approaches do not accumulate contributions from source pixels in the target image but, conversely, perform a direct look-up for each target pixel in the source image. In order to evaluate the analytical resampling expression without using Gaussian lters, the anti-aliasing lter is usually replaced by a practical anti-aliasing technique. The resampling expression simplies to an interpolation in source space. There exist a variety of dierent lter kernels that can be used for the interpolation, such as nearest-neighbor, bilinear, bicubic, or windowed-sinc interpolation kernels. In the quality evaluation section, the performance of the interpolation kernels is evaluated and compared numerically to each other.

The general backward evaluation formula can be written as

ρ h = k w k f i (m -1 (x h ) -u k ). (8)
For instance, in the simple case of nearest-neighbor interpolation, the expression becomes

ρ h = w k with k = argmin k |m -1 (x h ) -u k | 2 .
Expressions for other interpolation lters can be derived similarly or looked-up in literature [START_REF] Wolberg | Digital image warping[END_REF].

To add anti-aliasing on top of the practically ecient backward interpolation technique, dierent approaches exist. One is super-sampling and decimation, where image values are looked-up on a higher-resolution output grid and then decimated again to the actual required resolution. The decimation lter thereby serves as anti-aliasing lter. Another technique is mip-mapping, which is used in the texture mapping stage in current GPUs [START_REF] Akenine-Moller | Real-time rendering[END_REF]. Mip-mapping keeps multiple resolution of the same image and, during look-up, uses the resolution that corresponds to the local downscale/upscale factor. [START_REF] Chang | A 94fps view synthesis engine for HD1080p video[END_REF] Evaluations

The general resampling framework described above allows many practical realizations, in particular when selecting interpolation lters and the anti-aliasing method. In this section we compare several common methods in terms of visual quality, and, more importantly, in terms of computational complexity. Finally, we evaluate memory accesses and design a cache to reduce memory bandwidth for non-linear image domain warping applications.

d) Isotropic minification

Fig. 2. Comparison of PSNR values for dierent kind of transformations. The evaluations have been performed by rst applying a transformation and then the corresponding inverse transformation. The resulting image is compared with the original using the PSNR metric. The results plotted here are median values over a set of 16 natural 720p color images. The Gaussians are parameterized with σ = 0.39 in the above evaluation (this value was determined in [START_REF] Greisen | Analysis and vlsi implementation of ewa rendering for real-time hd video applications[END_REF]) and they are clipped at 2. The two EWA splatting variants (c,e) hardly show aliasing artifacts. We also observe that adaptive EWA splatting (e, see Section 2.2) provides a sharper image than conventional EWA splatting (c).

Quality Comparisons

For the evaluations we use several well-known interpolation and anti-aliasing methods and apply them to aspect-ratio retargeting and stereo-to-multiview conversion examples. Interpolation kernels compared in this work are bilinear and bicubic interpolation, b-spline, bicubic spline interpolation, Gaussian, and windowed-sinc lters with Hann and Lanczos windows. For details on the different methods refer to e.g. [START_REF] Wolberg | Digital image warping[END_REF]. Anti-aliasing kernels in forward mapping are evaluated using the EWA framework. Backward mapping methods are evaluated with various degrees of constant super-sampling (SS) or dierent sampling patterns such as quincunx and ipquad [START_REF] Akenine-Moller | Real-time rendering[END_REF].

Figure 2 provides evaluation results on comparing interpolation lters and anti-aliasing methods in resampling applications. The dierent resampling methods are used to transform a set of 16 natural 720p color images according to simple parameterized transformations (e.g. rotation by a certain angle). In order to be able to assess the resampling quality using the PSNR measure, the images are resampled twice: once with the forward transform and once with the corresponding inverse transform. The original images can then be used as a reference. It should be noted that the PSNR is a good measure for the amount of introduced blurring, but it does not capture aliasing artifacts very well as can be seen in Figure 2d, which shows the numerical results for isotropic minication.

From these basic quality evaluation gures, several observations can be made. The rst observation is that Gaussian interpolation shows similar quality compared to the typically used bilinear interpolation, even without any non-linear warping. Bicubic methods and windowed sinc lters are in general superior to Gaussian and bilinear interpolation, and B-splines show the worst performance.

Regarding anti-aliasing, one observes two things: the numerical evaluations show that all methods introduce a similar amount of additional blurring, except of course, when using no anti-aliasing method. The adaptive Gaussian shows less blurring than the xed-width Gaussian, which has been already shown in Section 2.2. On top of that, visual evaluations show that using no anti-aliasing lter may introduce severe aliasing artifacts, as can be seen in Figure 3.

Our observations are in line with claims and evaluations from previous works [START_REF] Akenine-Moller | Real-time rendering[END_REF][START_REF] Heckbert | Fundamentals of Texture Mapping and Image Warping[END_REF][START_REF] Szeliski | High-quality multi-pass image resampling[END_REF][START_REF] Triggs | Empirical lter estimation for subpixel interpolation and matching[END_REF]. Quality-wise, we conclude that the adaptive EWA splatting approach is superior both to simple bilinear interpolation and bilinear interpolation with super-sampling. In terms of quality, a bicubic or windowed-sinc backward mapping approach with (sucient) supersampling are superior to EWA splatting.

Computational Complexity

Beside the quality evaluations, we compare the computational complexity of bilinear and bicubic backward mapping as well as adaptive EWA splatting in image domain warping applications (e.g., aspect ratio retargeting). We consider the following scenarios, rst an identity transformation of a 1920 × 1080 image, Top: identity transformation; middle: 4:3 to 16:9 retargeting using linear scaling; bottom: 16:9 to 4:3 retargeting using linear scaling. The compared methods are bilinear interpolation (Bil), bicubic convolution (BicConv ) and adaptive EWA splatting (adEWA). The postx SSx2 stands for twofold supersampling, whereas noAA stands for no anti-aliasing. The methods printed with a bold font do not include any warp preprocessing, whereas the methods with the postx WarpInv1081, WarpInv100 or In-terp100 include an additional warp inversion or warp interpolation step (the number denotes the vertical warp resolution -refer to the text for more details).

second linear scaling from 1440 × 1080 to 1920 × 1080, and third linear scaling from 1920 × 1080 to 1440 × 1080. Using these three cases, the order of magnitude of the complexity can be estimated. More importantly, these cases allow us to compare the relative complexity of dierent methods. As can be seen in Figure 4, the lowest-cost technique is bilinear interpolation (Bil+noAA), followed by bicubic interpolation (Bic+noAA) and adaptive EWA (adEWA). We also see that supersampling signicantly increases the complexity of the backward mapping methods. Note that the bicubic polynomials and the Gaussian kernel evaluations are approximated with linear interpolation between lookup table values. Further, the inverse square-root is calculated using the fast inverse square-root approximation [START_REF] Lomont | Fast inverse square root[END_REF].

Warp Interpolation and Inversion The numbers discussed above hide a practical issue: depending on the application, warp information is available in either forward or backward format and the conversion from one format to another requires additional computations. In typical image domain warping applications, warps are available in forward format. This has consequences for backward mapping approaches, where an additional inversion step becomes necessary (denoted as Inv1081 in Figure 4). Further, the warp is usually available on lower resolution than the actual image such that an additional upscaling step using interpolation is necessary (e.g. bilinear interpolation). Warp inversion together with warp upsampling from 100 pixel to 1080 pixel in vertical direction is denoted as Inv100 whereas, warp upsampling alone is denoted as Interp100. Note that the warp inversion also requires more memory (and associated bandwidth) for the storage of the inverted warp coordinates or the partly rasterized output image.

Conclusion Together with the quality evaluations from the previous section, we conclude that adaptive EWA splatting forms a good tradeo between computational complexity, interpolation and anti-aliasing quality. Bilinear interpolation lowers the computational complexity but at the price of lower image quality. Finally, bicubic approaches provide more interpolation quality at a similar cost as EWA splatting, but they are very costly when super sampling is added. In image domain warping applications, forward warp coordinates are available, which makes EWA splatting an ecient solution for non-linear warping.

Memory Bandwidth Evaluation

In real-time VLSI implementations, the warp and image are processed in scanline order. Depending on the warp format, i.e., backward or forward transformation, the image needs to be stored in either input buer or an output framebuer, in order to support arbitrary image transformations. The buers usually contain large parts or the entire image and therefore have to be stored in external ochip memories (an uncompressed full HD image amounts to about 50 Mbit). Due to the limited pin and power budget it is important to minimize the required memory bandwidth. Target Space Source Space Legend Fig. 5. This gure shows a typical frame buer access pattern of a retargeting warp rendered with EWA splatting. The grid on the left hand side shows a typical retargeting warp of a 1280 × 720 image. In this application, the warp contains only limited image distortions. The excerpts on the right side show close-ups of two partially rendered regions of this warp, where the large spatial overlap among subsequent patches in horizontal and vertical directions can be observed.

Bandwidth Bottleneck In the case of backward mapping, each rendered output image pixel requires a small patch to be fetched from the input image in order to perform the interpolation. Similarly, in the case of a forward mapping method, each input image pixel leads to a patch of pixel contributions in the output image, which are then accumulated in a frame buer. In both cases the size of those patches depends on the employed lter kernel, and ranges from 2×2 (bilinear and adaptive EWA), to 3 × 3 (normal EWA) to 4 × 4 pixels (bicubic).

Thus, the amount of memory accesses is a multiple of the image resolution and can easily lead to a bandwidth bottleneck. For instance, in the case of bicubic interpolation and a 1080p color output image we require a bandwidth of 1920 × 1080 × 3 × 4 × 4 ≈ 796 MByte/frame. Fortunately, if the warp is traversed in scanline order, consecutively accessed patches spatially overlap to a certain degree as illustrated in Figure 5. The vertical and horizontal locality of the patches can be leveraged to reduce the overall bandwidth by employing a two-dimensional image cache (similar to texture caches in GPUs).

Cache Evaluations In order to see how a two-dimensional image cache has to be parameterized in the case of image warping, we simulated dierent cache congurations for dierent resampling methods and calculated the required bandwidth for one frame. Figure 6 shows the averaged simulation results of a direct mapped cache with degenerate 1 × 1 blocks for 17 nonlinear retargeting warps (aspect ratio change from 4:3 to 16:9 for 1080p images). Note that the retargeting warps all show similar memory access patterns as they perform the same global linear upscaling with only local variations. For better readability, the bandwidth has been normalized with the size of the input image (a), or with the size of the output image (b) depending on the mapping direction (forward or backward). We can see that as soon as the cache is large enough to store an image patch which is larger than the size of the employed lter kernel (4 × 4 in (a) and 3 × 3 in (b)), the bandwidth is beginning to drop signicantly. In the ideal case, if the cache is large enough, data will be transferred only once between the main memory and the cache. This corresponds to transferring only one input image to the cache in a backward mapping architecture, and only one output image in a forward mapping architecture. In this optimal case the normalized bandwidth is equal to one. As can be seen in Figure 7 and Figure 8, the optimum can be reached if the cache is large enough to hold several image rows.

A cache with a block size of 1 × 1 pixel is adapts well to the geometric variations in the warp function, but such a cache conguration requires a huge amount of overhead (i.e., valid-bit and address-tag entries have to be stored for each pixel as well). Increasing the block size reduces the memory required to store the tags and the valid-bits, but also comes at the cost of cache performance, as can be seen in Figure 7 and Figure 8. However, if the cache is large enough, it is possible to reach the optimum with large cache blocks. [START_REF] Cummings | Simulation and synthesis techniques for asynchronous fo design[END_REF] Hardware Architectures

Based on the ndings from the previous section, we introduce two hardware architecture for spatially-varying image warping. The rst architecture uses forward mapping with adaptive EWA, the second architecture uses backward mapping with bicubic interpolation and, to reduce computations, with an adaptive super-sampling technique. The top-level diagram of the EWA architecture is given in Figure 9. The core accepts streaming pixel color information, given in an 24 bit RGB format. In addition to the color information, a deformation grid describing the pixel mapping m is streamed in. In the quadrilateral deformation grid format, the deformation of each pixel is described by transformation of the pixel's bounding box. More specically, the four corner positions of a quad describe the new pixel center as well as the pixel deformation. The horizontal and vertical gradients necessary for constructing J k can be easily deduced from the quads.

We assume that the image transformation m is locally smooth, and that neighboring pixels share their adjacent quad grid corners. Therefore, in compact form, the quad grid representation only requires (W + 1) × (H + 1) grid points, if W and H are the input video width and height, respectively. Note that we chose this representation in order to disallow transformations that would result in image holes. Furthermore, since neighboring grid points and pixels are typically strongly correlated, we add a lossless dierential compression/decompression scheme at the input interface to reduce the input bandwidth and I/O power. Note that temporal compression across frames could further reduce the input bandwidth since the warp typically varies slowly over time.

From the input quad grid, the pixel position m(u k ) (mean of adjacent corner positions) and the Jacobi matrix J k (horizontal and vertical gradients computed from the corner positions) are calculated and stored in an on-chip FIFO buer. A dispatcher unit then distributes positions, Jacobian, and pixel values to multiple arithmetic units that perform the splatting operation. The processing time of each splatting operation strongly depends on the deformation, as one input pixel can possibly be stretched to multiple output pixels. To handle the variable throughput requirements, several arithmetic splatting chains are used in parallel, and the dispatcher unit distributes the input pixels depending on the workload. A FIFO buer can absorb incoming pixels when all splatting units are occupied during performance peaks. To handle prolonged peaks, the FIFO res a back-pressure system that allows to stall the data source to avoid data loss.

Due to mathematical properties of the summation operation in (5), we can rearrange the operation: instead of evaluating the sum for each output position, we forward-transform all individual Gaussian kernels and perform an accumulation of the Gaussian contributions in the temporary output image. To avoid excessive memory bandwidth requirements between the chip and the external frame buer, we employ a two-level cache structure, in accordance with the cache conguration simulations presented in the previous section. The cache exploits the spatial coherence of image transformations, which in general map neighboring input pixels to neighboring output pixels.

When all input pixels have been processed, the temporary output image can be streamed to a normalization unit, where the accumulated pixels are then normalized by the sum of the lter weights. Note that this nal normalization step is necessary due to the fact that Gaussian lters, and in particular their truncations, are non-ideal interpolation lters. Input Interface The system requires the pixel information and the deformation grid as the input. Since the deformation grid has to be determined by another computation block, a simple custom interface has been designed that can easily be adapted for dierent applications.

Compression The input interface consists of 24 bit RGB values and 2 × 24 bit pixel coordinates, resulting in a bandwidth of 4.5 GBit/s for 1080p30. To Dispatcher The dispatcher unit is responsible for load-balancing between multiple subsequent splatting units. A simple round-robin based priority scheme is used for the scheduling.

Arithmetic Processing Elements In a nutshell, the splatting units implement the EWA equation ( 5) in a xed-point format. For each input pixel, a Gaussian kernel is calculated from the pixel color w k and the linearized approximation J k of the warp grid. The Gaussian kernel is then resampled to determine its contribution to all output pixels. The resampling is evaluated within a small bounding box of the Gaussian only, i.e., the Gaussian will be truncated to zero as soon as its energy falls below a very small threshold. The contributions of the individual Gaussians are then accumulated, and nally normalized. The datapath is implemented using custom xed-point arithmetic. The accumulated color channels are calculated with 11 bits each, and the accumulation values are calculated with 12 bits, resulting in data words of 45 bits in total for each pixel. This number has been chosen both for accuracy reasons as well as to match the word-width of the external memory.

Adaptive EWA The splatting cores can be congured to work in 'adaptive' mode, which means that the Gaussian resampling covariance matrix is adapted perpixel to reduce the amount of blurring. The adaptive mode has been introduced in [START_REF] Greisen | Analysis and vlsi implementation of ewa rendering for real-time hd video applications[END_REF] and its impact on overall area is negligible.

Throughput Each splatting unit has a xed throughput Θ = f /n cycles , determined by the clock frequency f and the number of cycles required to evaluate one input pixel n cycles . The current architecture is optimized for n cycles = 20, which is matched to the average number of output pixels times the number of cycles it takes to evaluate one output pixel (9 × 2 plus overhead). A throughput of 9 MPixels/s per splatting unit at a clock frequency of 170 MHz can be achieved. Therefore, 1080p30 video (63 MPixels/s) can be achieved with some margin by employing 8 parallel splatting units.

Accumulation, Caching, and Memory Interface Each input pixel produces several output contributions that need to be weighted by a Gaussian kernel and accumulated at the output sampling locations. As described earlier, the Gaussian kernels are truncated at the bounding box boundary, and simulations have shown that bounding boxes of 4 to 9 pixels in size are sucient to capture the majority of the non-zero contributions. Hence, the accumulation bandwidth is between 2 × 4 and 2 × 9 times larger than the input bandwidth, as each accumulation is performed using a read-modify-write operation. To reduce the external bandwidth, our on-chip caching architecture exploits the horizontal and vertical overlaps of neighboring Gaussian kernels. In a rst stage (denoted L1), contributions with spatial proximity are collected and accumulated into larger blocks. The L1 blocks are then eciently accumulated to a second stage (L2 blocks). The L2 cache is able to store several lines of the image, and once a line is removed from the L2 cache it is accumulated to the external frame buer memory. Our two-stage caching architecture reduces the resulting bandwidth considerably: the L1 cache is implemented using register arrays that support the highest bandwidth, and the L2 cache implemented using block RAMs that reduce the bandwidth to external memory further.

Throughput Each accumulated data word has 45 bits, the required bandwidth for 1080p30 can be calculated as

bw full = 45 × 1920 × 1080 × 30 × 2 × (1 + n pps ),
where the factor 2 comes from the read-modify-write operation. n pps denotes the number of pixels per splat, i.e., the bounding box size. Additionally, the nal read out requires one more read from the memory. If we assume a conservative value of n pps = 9, the overall bandwidth equals bw full = 56 Gbit/s. Our cache architecture exploits the inherent spatial overlap between neighboring pixels, and shifts the bandwidth burden to the on-chip buers, reducing the eective n pps . In simulations, a cache eciency resulting in n pps = 3 is always achieved, and the required bandwidth is reduced to 22.4 Gbit/s. Due to the read-modify-write operation, we choose a QDR-type memory interface to eciently support the accumulation. QDR memories are static RAMs that have separate read and write ports, which can be accessed in parallel. Moreover, the data is transmitted in double edge mode. A 9 bit QDR RAM port therefore has 3 Gbit/s read and 3 Gbit/s write bandwidth, at a clock frequency of 170 MHz. Our architecture employs 5 instances of such 9 bit RAM interfaces, and the resulting 45 bit memory interface matches our data word size. The overall available bandwidth therefore amounts to 30 Gbit/s.

MAC unit J k m(u k ) J k J k ' |C| C |C| -0.
Scheduling and Control Flow Due to the varying bounding box sizes of the input Gaussian kernels, the run-time of the individual rendering cores is non-deterministic during operation. However, on a per-frame basis the varying per-pixel run-times are averaged out and thus approximately constant, which can be used for dimensioning the number of cores and the required memory bandwidth. Short-term uctuations of throughput are then regulated using a back-pressure system. Moreover, an ecient scheduling strategy distributes the input pixels to individual rendering units.

Output Interface The nal step of the rendering pipeline consists of reading out the image from the frame buer and interfacing it to a standard display chip. Since display interfaces must adhere to a very strict timing, the read-out from the frame buer is always prioritized over the read-modify-write accumulation operations. In case of collision, the accumulation can be stalled via the backpressure mentioned before. The normalization block contains a divider producing Figure 11 provides a top-level architecture overview of backward mapping using bicubic interpolation and two-times adaptive super-sampling. The high-level architecture is conceptually similar to the EWA architecture shown in Figure 9.

The backward warping grid represented by Jacobian and backward coordinate lookup values is streamed line-by-line into the warping core (no warp inversion is performed here). However, contrary to the EWA forward architecture, the pixel intensities are not streamed together with the warp grid, but are accessed through an external buer.

reduced, and second, blurring due to super-sampling with non-ideal decimation kernels is avoided where no anti-aliasing is necessary. The currently employed supersampling strategy could be further improved by introducing directional super sampling, i.e., by applying super sampling only in the direction where the potential aliasing appears. This extension is able to provide a higher throughput in cases where the image transformation is demagnifying and anisotropic (e.g. an aspect ratio change from 16:9 to 4:3).

Bicubic Interpolation The adaptive super-sampling block outputs backward coordinates to the memory interface block responsible for fetching the corresponding pixels from the external buer. In parallel, the interpolation arithmetics block gets the fractional part of the backward coordinates to set up the bicubic lter kernel coecients. For each output sample, an area of 4 × 4 pixels has to be multiplied with the bicubic kernel. Note that this kernel is separable and thus can be implemented with four vertical-and one horizontal application of the one-dimensional bicubic convolution kernel. This architecture uses xed point arithmetic throughout. The coecients of the bicubic kernel can therefore be directly obtained from two lookup tables (LUTs), where we the indices consist of two integer bits and the fractional bits of the x and y coordinate dierences, respectively. If the fractional precision is not too large, no additional renement of the indexed values (e.g. using linear interpolation) has to be performed as the LUTs already cover the whole index range. The throughput of the bicubic interpolator is one pixel per 4 cycles. In order to produce a super-sampled output pixel, four such samples have to be calculated and averaged and thus 16 cycles are required in that case. Thus, the eective throughput of the interpolator depends on the fraction of supersampled pixels per frame.

Caching and Memory Interface Analogue to the forward mapping architecture, the amount of accessed input image pixels is very large as the bicubic interpolator always accesses a 4 × 4 neighbourhood in order to calculate an output pixel. Thus even in the case of no supersampling, we would have to load 16 times more pixels than there are in one frame, which translates into a very large external bandwidth. An on-chip read cache which is able to hold several lines of the image is therefore employed to reduce the bandwidth. As the bicubic interpolator requires 4 cycles to produce one output sample, the cache memory is divided into four column interleaved RAM macros such that four parallel accesses are possible.

Implementation Results

Several ASIC implementations of non-linear warping architectures have been realized which allow for a comparison and conclusion on hardware performance of the dierent techniques. In the following, we discuss some of the implementation results of the dierent ASICs. In order to reach the optimal cache eciency for 720p25 video, the cache should be extended to 8 lines with 1280 pixels per line (see Section 3.3). Note that in addition to the above bandwidth, a read/clear operation to the memory is further necessary to account for the nal read-out and clearing.

EWA Splatting: Vesper

The Vesper chip is an extended version of Esper, and it is designed to render full HD color images at 30 frames per second. In contrast to Esper this chip has been fabricated in 130 nm CMOS and it is equipped with fully-functional display-and memory interfaces (Figure 12(c)).

The DVI interface requires a xed input bandwidth and clock frequency, which usually is dependent on the display resolution and frame rate. To decouple the arithmetics and accumulation from the DVI interface, we separate the design into two clock domains. While the rendering core should run as fast as possible, the DVI core is running at the specic DVI pixel clock. The asynchronous data interface is implemented using an asynchronous FIFO, see [START_REF] Cummings | Simulation and synthesis techniques for asynchronous fo design[END_REF]. The chip also provides clock signals for the external RAM components and the DVI transmitter. In order to provide a exible timing at the corresponding interfaces, those output clocks can be phase shifted relative to the internal clock signals.

The I/O bandwidth, the throughput of the splatting units and the caching have been dimensioned for very pessimistic and demanding scenarios, such that 1080p30 performance is achieved in a practical system that supports a wide variety of warping applications. In turn, the actual performance for typical applications will be higher, and therefore also higher frame rates are possible. Under typical conditions, our architecture reaches 1080p48. Furthermore, smaller resolutions are always possible and would increase the frame rate further (e.g. 720p60).

The chip area is largely dominated by the number of input and output pins, as well as the required power distribution for the high speed I/O interfaces. Vesper supports 175 data I/O pins, of which 115 pins are used for the external QDR-II interface. Due to the prototype nature of the chip, a more conventional "around the core" I/O has been employed, instead of a more area ecient ip-chip I/O. For a commercial implementation, the area could be signicantly reduced since the overall logic area (including on-chip SRAM) is 9 mm 2 which is much smaller than the 5 × 5 mm 2 the chip currently occupies. The chip contains a similar cache conguration as Esper (8 × 1024 pixel) with approximately half of the access bandwidth: backward mapping only requires a read operation whereas the accumulation process in forward mapping requires a read-modify-write operation. Thus, a single port memory is sucient which reduces SRAM size by half. Further, the entries are only 8 bit wide, and no accumulation weights have to be stored. Thus, in total, the SRAM memory macro is about four times smaller in size. Note however, that this factor of four reduces to a factor of around 1.83 if RGB pixels are stored (EWA shares the weight entry among the three color subpixels), and if the accumulation precision is changed to a more realistic value of 11 bit.

Comparison

In Table 1, we list several warping VLSI architectures to compare computational resources. As can be seen, the EWA warping core is signicantly larger than comparable backward architectures such as Eva and [START_REF] Huang | A novel interpolation chip for real-time multimedia applications[END_REF][START_REF] Lin | A low-cost VLSI design of extended linear interpolation for real time digital image processing[END_REF]. In particular, the cache of the EWA implementations is larger due to the higher xed-point precision, the additional weight entry, and the read-modify-write type operation. Another reason for the higher gate count of the EWA implementations is that the EWA arithmetics are fully evaluated, whereas a signicant portion of computations in the bicubic implementation are optimized by using LUT-based approximations. Note that the EWA architecture could also be optimized by replacing some of the arithmetic units with look-up tables. Thus, in applications where warping information is available in backward format and aliasing is of limited concern, one should clearly prefer a backward mapping architecture, e.g. bicubic or bilinear interpolation.

Conclusions

Arbitrary transformations of high-denition videos can be eciently rendered using a non-linear warping VLSI architecture. The proposed VLSI cores can be used in an end-user device and enable image warping for current and upcoming content-adaptive applications. Due to the separation of the rendering core into several sub-units, the computational capabilities are easily scalable to higher resolutions and frame-rates, such as the upcoming quad HD standards (2160p) or the high-frame rate (HFR) standards.

Fig. 3 .

 3 Fig. 3. Visual comparison of anti-aliasing artifacts: without anti-aliasing visual distortions are obvious (a); twofold oversampling removes some of the aliasing in this example (b). However, fourfold oversampling is necessary to remove all aliasing (d).The two EWA splatting variants (c,e) hardly show aliasing artifacts. We also observe that adaptive EWA splatting (e, see Section 2.2) provides a sharper image than conventional EWA splatting (c).

Fig. 4 .

 4 Fig.[START_REF] Cummings | Simulation and synthesis techniques for asynchronous fo design[END_REF]. Comparison of the computational complexity of dierent resampling techniques. Top: identity transformation; middle: 4:3 to 16:9 retargeting using linear scaling; bottom: 16:9 to 4:3 retargeting using linear scaling. The compared methods are bilinear interpolation (Bil), bicubic convolution (BicConv ) and adaptive EWA splatting (adEWA). The postx SSx2 stands for twofold supersampling, whereas noAA stands for no anti-aliasing. The methods printed with a bold font do not include any warp preprocessing, whereas the methods with the postx WarpInv1081, WarpInv100 or In-terp100 include an additional warp inversion or warp interpolation step (the number denotes the vertical warp resolution -refer to the text for more details).

Fig. 6 .

 6 Fig.6. Simulation of dierent overall cache sizes of a direct mapped cache with degenerate 1 × 1 blocks (i.e. each pixel has its tag and valid bit). Both plots show the averaged results from 17 nonlinear retargeting warps (aspect ratio change from 4:3 to 16:9 of 1080p images).(a) shows the normalized bandwidth of the input image buer for bicubic backward mapping; and (b) shows the normalized bandwidth of the frame buer for (non-adaptive) EWA splatting. The normalized bandwidth is encoded in the color. Depending on the mapping direction of the method, the normalization factor is either the size if the input (a) or output image (b).

Fig. 7 .

 7 Fig. 7. Simulation of dierent cache congurations for the input image buer used in bicubic backward mapping. (a) shows the results for a nonlinear aspect ratio change from 4:3 to 16:9 of a 1080p image; and (b) shows the results for a nonlinear aspect ratio change from 16:9 to 4:3 of a 1080p image. The results are mean values over 17 warps generated for natural testimages.

Fig. 8 .

 8 Fig. 8. Simulation of dierent cache congurations for the frame buer used in EWA splatting. (a) shows the results for a nonlinear aspect ratio change from 4:3 to 16:9 of a 1080p image; and (b) shows the results for a nonlinear aspect ratio change from 16:9 to 4:3 of a 1080p image. The results are mean values over 17 warps generated for natural testimages.

Fig. 9 .

 9 Fig. 9. Top level block diagram of the EWA rendering architecture.

Fig. 10 .

 10 Fig. 10. Data path of the EWA splatting core.

Fig. 11 .

 11 Fig.11. Block diagram of bicubic interpolation with adaptive 2× super-sampling. The caching setup is similar to the EWA rendering architecture cache, since a similar access pattern is assumed. The key dierence is that the bicubic backward mapping cache is a read-buer whereas the EWA forward mapping cache uses (read-modify)-write accesses.

5 . 3 Bicubic

 53 Interpolation: Eva A bicubic backward mapping ASIC named Eva has been fabricated in 180 nm CMOS technology (Figure 12(b)), and it has been designed to roughly match the specications of the Esper ASIC such that the two implementations are comparable. It is able to support enough throughput for 576p25 when 10% of the calculated pixels are super-sampled. Typical case post-layout simulations have shown a maximum operating frequency of 135 MHz and a power consumption of 60 mW. The core area is around 1 mm 2 which correspond to 110 kGE.

Fig. 12 .

 12 Fig. 12. Photo and CAD rendering of our VLSI implementations: (a) Esper (180 nm), (b) Eva (180 nm) and (c) Vesper (130 nm). The pictures are not to scale.

  The ASIC has been successfully tested at 123 MHz where a power consumption of 300 mW has been measured. Core voltage is 1.8 V and I/O pad voltage is 3.3 V. Core area is 6 mm 2 which corresponds to 660 kGE. There are 64 data I/O and 56 power/ground pins. This chip is a prototype of the EWA core architecture and does not possess a real-world memory interface. The normalization block is also not included. The accumulation precision is set very conservatively to 16 bit per entry.Detailed Throughput Figures For the following throughput gures, a nominal clock frequency of 133 MHz is assumed. One splatting unit has a throughput of 6.65 MPixels/s. A 720p25 video stream requires a throughput of 23 MPixels/s and thus four splatting units. The necessary external memory bandwidth without caching is 2 × 9 × 23 = 414 MPixel/s which amounts to 414 × 4 ≈ 1.66 GByte/s for 4 bytes per pixel entry (accumulated value plus normalization weight). The factor 2 comes from the read-modify-write operation of the accumulation. The cache has an eciency of about 83% which reduces the external bandwidth to 282 MByte/s, i.e. the normalized bandwidth is around 1.5 (normalized to the bandwidth it takes to read, modify and write one output image). The optimum normalized bandwidth cannot be reached, as the cache is only 1024 pixels wide.

	5.1	EWA Splatting: Esper
	The EWA architecture described previously was implemented in VHDL and
	was fabricated in 180 nm (1P6M) CMOS technology (Figure 12(a)). The design
	supports image resolutions up to 2048×2048 and works on gray-level 8-bit pixels.
	It employs four splatting units to support 720p25 in splatting performance. Due
	to die size limitations the cache is reduced to eight lines of gray-valued 576p
	(i.e. 8x1024 pixels).

Table 1 .

 1 Comparison of dierent warping CMOS implementations. The rather large dierences in size originate from the type of transformation that are supported: arbitrary (arb.) or simple linear scaling (lin. scal.). In addition, EWA and bicubic feature full or partial (super sampling (SS)) anti-aliasing support. Note that for the EWA architecture, the interpolation (interp.), anti-aliasing (AA), and transformation (transf.) blocks cannot be separated for the area numbers. A '' means that the architecture does not contain such a block, N/A means that the values are not available. The external bandwidth gures are typical case values, normalized to reading/writing an image once. The maximum throughput of our implementations are evaluated valid for nonlinear resizing (change of aspect ratio from 4:3 to 16:9). Results marked with (*) are obtained through postlayout simulations.

		EWA Esper	Bicubic Eva	Ext. Bil. Ext. Bil. [15] [12]
	Anti-Aliasing	yes	2×SS	no	no
	Transformation	arb.	arb.	lin. scal. lin. scal.
	Mapping direction	fwd.	bwd.	bwd.	bwd.
	Image resolution	576p	576p	1080p WQSXGA
	Color channels	1	1	1	1
	Technology [nm]	180	180	130	130
	Max. clock freq.[MHz]	123	135*	267	278
			47 (0%SS)*
	Max. throughput [fps]	40	28 (10%SS)*	N/A	30
			12.5 (100%SS)*
	Power [mW]	300	62*	18.1	11.7
	Transformation [kGE]	≈ 115	6	N/A	N/A
	Interpolation [kGE]	≈ 115	10	N/A	N/A
	Total w.o. memory [kGE]	230	16	26	13
	Buer size [Bit]	1024 × 8 × 2 × 16 1024 × 8 × 8		4 lines
	Buer [kGE]	410	90		N/A
	Memory type	DP SRAM	SP SRAM		SRAM
	Normalized ext. BW	1	1	4	N/A

Adaptive Supersampling The adaptive super-sampling block decides for each warp input whether super-sampling is necessary or not, by detecting if the transformation is locally minifying. Minications are detected by checking if the determinant of the Jacobian is greater than one, or the determinant of the inverse Jacobian is larger than one, depending on which format is available at the input. In the case of supersampling, the locations of the additional sampling points are linearly approximated using the Jacobian and the lookup coordinate. Note that applying super-sampling in an adaptive way has two benets over applying super-sampling everywhere: rst, the amount of computations is signicantly


Davide Sabena
email: davide.sabena@polito.it

Luca Sterpone
email: luca.sterpone@polito.it

Matteo Sonza
email: matteo.sonzareorda@polito.it

On the Automatic Generation of Software-Based Self-Test Programs for Functional Test and Diagnosis of VLIW Processors

Keywords: SBST, VLIW processor, Fault Simulation, Fault Diagnosis

Software-Based Self-Test (SBST) approaches have shown to be an effective solution to detect permanent faults, both at the end of the production process, and during the operational phase. However, when Very Long Instruction Word (VLIW) processors are addressed these techniques require some optimization steps in order to properly exploit the parallelism intrinsic in these architectures. In this chapter we present a new method that, starting from previously known algorithms, automatically generates an effective test program able to still reach high fault coverage on the VLIW processor under test, while minimizing the test duration and the test code size. Moreover, using this method, a set of small SBST programs can be generated aimed at the diagnosis of the VLIW processor. Experimental results gathered on a case study show the effectiveness of the proposed approach.

Introduction

The continuous scaling in the semiconductor fabrication process combined with the progressive growth of the integrated circuits operation frequency pushes processor cores to face more difficult testability problems. Furthermore, several phenomena such as metal migration or aging become more likely, thus increasing the occurrence of permanent faults in the generic system, in particular during the circuit operational phase. For these reasons, in order to provide high fault coverage with acceptable costs, new test solutions are being investigated and evaluated (e.g., in terms of silicon area overhead, required test infrastructure and test time). Software-Base Self-Test (SBST) has been demonstrated to be a promising and effective approach for the test of processors and processor-based systems [START_REF] Psarakis | Microprocessor softwarebased self-testing[END_REF]. The SBST main idea is to generate test programs to be executed by the processor under test, able to fully stimulate the processor itself or other components belonging to the system, and to detect possible faults by looking at the produced results. The SBST technique does not require any additional hardware; therefore, the whole test cost is reduced and no performance penalty is introduced. Moreover, the SBST technique allows at-speed testing and can be easily used even for on-line test purposes. Hence, processor and System on Chip (SoC) testing approaches are increasingly adopting SBST techniques, often in combination with other approaches.

Correct identification of the most common defective parts in a SoC helps to characterize the technological process. The localization of a fault allows to effectively direct physical investigation of the underlying defects [START_REF] Bernardi | An Effective Technique for Minimizing the Cost of Processor Software-Based Diagnosis in SoCs[END_REF]. Moreover, a good diagnosis capability is fundamental for the devices containing self-repair skills. On the other side, it is well known that the complexity of diagnostic test generation is much higher than that of detection-oriented test generation [START_REF] Chen | Software-Based Diagnosis for Processors[END_REF]. Among the various diagnosis techniques, the Software-Based Diagnosis (SBD) methodology has turned out to be a suitable solution for processor cores embedded in SoCs [START_REF] Bernardi | An Effective Technique for Minimizing the Cost of Processor Software-Based Diagnosis in SoCs[END_REF] [START_REF] Chen | Software-Based Diagnosis for Processors[END_REF].

Today, several applications demand for high performance while exposing a considerable amount of Instruction Level Parallelism (ILP), such as Digital Signal Processing [START_REF] Fisher | Embedded computing: a VLIW approach to architecture, compilers and tools[END_REF]: among the various microprocessor architectures, Very Long Instruction Word (VLIW) processors have been demonstrated to be extremely attractive for such kinds of applications. Nowadays, several products for embedded applications adopt VLIW processors; therefore, the problem of testing them is increasingly relevant.

A major difference of VLIW processors with respect to traditional superscalar processors is the instruction format. Several VLIW instructions, named microinstructions, are grouped into one large macro-instruction (also called bundle) where all micro-instructions within the bundle are executed in parallel computational units; each one is independent and referred to as Computational Domain. The operation scheduling performed by VLIW architectures is executed at compile time; therefore, the compiler is responsible for allocating the execution of each instruction to a specific Functional Unit (FU).

Due to these characteristics, VLIW processors are suitable for safety-critical systems adopted in mission-critical applications such as space, automotive or railtransport fields which require computationally intensive functionalities combined with low power consumption. For example, the processor Tilera TILE64TM, composed of several VLIW cores, is used to efficiently perform image analysis on-board a Mars rover in support of autonomous scientific activities [START_REF] Bornstein | Using a multicore processor for rover autonomous science[END_REF] [START_REF] Corporation | Multicore Development Environment User Guide[END_REF].

Few previously developed SBST approaches may be found in the literature in order to properly test VLIW processors against permanent faults; more in particular, part of them rely on suitable instructions belonging to the original processors instruction set to apply the test patterns previously generated by automated test pattern generation (ATPG) tools, which particularly focus on internal components [START_REF] Beardo | An approach to functional testing of VLIW architectures[END_REF]. These methods present some drawbacks: first of all, transforming the test patterns generated by the ATPG into test programs is not always straightforward; secondly, the resulting test programs are not optimized, especially in terms of test duration; finally, the attainable fault coverage is rarely as high as it may be required.

VLIW processors include a register file having some characteristics (in particular, the fact that it can be accessed from different domains) that make it different than the one in other processors. In [START_REF] Sabena | A new SBST algorithm for testing the register file of VLIW processors[END_REF] we focused on this component and proposed a solution, based on a SBST approach, which resulted to be quite effective.

Considering the diagnosis problem in VLIW processor, in the literature there is only a preliminary work aimed at the localization of permanent defects inside VLIW components, and the provided solution is a combination of several self-test techniques (SBST and BIST) [START_REF] Ulbricht | A New Hierarchical Built-In Self-Test with On-Chip Diagnosis for VLIW Processors[END_REF].

In this chapter we focus on the generation of effective SBST test programs for VLIW processors, characterized by minimal size, minimal duration and maximum fault coverage. The proposed method starts from existing SBST test programs developed for the different FUs embedded into most processors (e.g., ALUs, adders, multipliers and memory units). Although the characteristics of FUs used within a VLIW processor are similar to those used in traditional processors, generating optimized code to effectively test these units is not a trivial task: our test generation procedure addresses the several units embedded into distinct parallel computational domains, thus taking into consideration the inherently parallel architecture of VLIW processors. Another goal of our work was the development of a general approach that could lead to the automatic generation of the test program for a VLIW processor, once the test code for testing each unit is available, and the processor configuration is known. The architecture of a VLIW processor does not include any custom hardware module, but rather a combination of common Functional Units. Our solution allows test program generation and optimization to be performed autonomously, while automatically exploiting the VLIW characteristics, without any further manual effort. The proposed method allows to generate highly optimized test programs which exploit most of the VLIW processor features and are aimed at minimizing the test time and the test program size. Besides, the method does not require the usage of any ATPG tool, since it is fully functional. Finally, without any additional effort, it is possible to exploit the test programs developed during the proposed flow to perform fault diagnosis and thus identify the faulty unit among the most relevant modules of the considered VLIW processors.

The main contribution of this chapter is the description of the first technique able to completely automate the generation of effective Software-Based Self-Testing programs for VLIW processors, while guaranteeing that the resulting programs are optimal in terms of duration and size. Exploiting this automatic method, test programs having some diagnostic properties can also be generated. The proposed method has been evaluated on a VLIW platform based on the Delft University ρ-VEX VLIW processor [START_REF] Wong | Dynamically reconfigurable register file for a softcore VLIW processor[END_REF] [START_REF] Wong | ρ-VEX: a reconfigurable and extensible softcore VLIW processor[END_REF] which supports most of the features of industrial VLIW architectures. The results we achieved clearly demonstrate the effectiveness of our approach. Considering the generation of the optimized test programs, clock cycles have been reduced by approximately 54% with respect to the original test programs, while the size of the optimized test program decreased by approximately 58%. When the diagnosis capabilities are considered, given a generic fault in the VLIW processor under test, we are able to distinguish it uniquely in the 2.78% of the cases; moreover, in 79.15% of cases we are able to identify the faulty module containing the fault itself, while in the remaining cases we are able to narrow down the set of candidate faulty modules to 2 modules (54.52%) or to 3 modules (38.81%).

The chapter is organized as follows. Section 2 gives an overview of the VLIW architecture. Section 3 describes the related work on Software-Based Self-Test techniques specifically oriented to VLIW processors, while Section 4 explains in detail the proposed method. Experimental results on the selected case study and their analysis are presented in Section 5. Finally, conclusions and future work are described in Section 6.

VLIW Architecture Summary

The main characteristic of a VLIW processor is the fact that all the operations are executed by parallel Computational Domains, each one characterized by its own Functional Units. Besides, the scheduling is totally static, since compile tools preliminary define it at compile time. As illustrated in Fig. 1, the assembly code for a VLIW processor is drastically different from the point of view of the machine code with respect to a superscalar processor: several instructions are grouped together in a single macro-instruction (named Bundle) and for each instruction there are some information items that allow to assign its execution to a specific Computational Domain. Consequently, in a VLIW processor there isn't any hardware instruction scheduler, and the tasks typically performed by this component are done by the compiler. The power consumption is thus reduced and the silicon area decreases if compared to traditional superscalar processors. Furthermore, the Instruction Level Parallelism (ILP) can be adequately exploited (at least in the case of data intensive applications) since a good compiler is able to decide which instructions can be executed in parallel by checking the entire program at compile time [START_REF] Sabena | A new SBST algorithm for testing the register file of VLIW processors[END_REF].

A generic VLIW processor parametric architecture may have a variable number of functional units (FUs), so that different options, such as the number and type of functional units, the number of multi-ported registers (i.e., the size of the register file), the width of the memory buses and the type of different accessible FUs, can be modified depending on the application requirements [START_REF] Fisher | Embedded computing: a VLIW approach to architecture, compilers and tools[END_REF]. All the characteristics of a specific VLIW processor are grouped together and are listed in the so called VLIW manifest. The manifest specifies the number of computational domains, the number and type of the Functional Units embedded into each computational domain, the size and access mode of the register file and any other feature that must be taken into account when developing the code for the processor.

Related Work

Methodologies that require an external tester to perform the test are infeasible without the use of very expensive Automatic Test Equipments (ATEs); however the increasing gap between maximum ATE frequencies and SoC operating frequencies makes external at-speed testing problematic and expensive; at-speed testing is needed because of failures detectable only when the test is performed at the device operating frequency. Moreover, external test often involves long time and significant efforts to introduce the required hardware and may be characterized by long test application times [START_REF] Kranitis | Software-based self-testing of embedded processors[END_REF]. While ATEs use external resources to perform testing task, BIST involves internal hardware resources: additional hardware and software are integrated into the circuit to allow it to perform self-testing. The usage of BIST leads to lower the cost of the complete test as well as the test time, maintaining or improving the fault coverage, at the cost of additional silicon area [START_REF] Sabena | A new SBST algorithm for testing the register file of VLIW processors[END_REF].

SBST techniques represent a special solution for on-chip testing [START_REF] Kranitis | Software-based self-testing of embedded processors[END_REF], since they adopt existing processor resources and instructions to perform self-testing without any intrusiveness. The main advantage of the SBST methodology is that it uses only the processor functionality and instruction set for both test pattern application and output data evaluation, and thus does not introduce any hardware overhead in the design. However, software-based self-test methods may require very long programs to achieve high fault coverage of the device under test, and require ad-hoc techniques for generating suitable test programs [START_REF] Psarakis | Microprocessor softwarebased self-testing[END_REF] [START_REF] Kranitis | Software-based self-testing of embedded processors[END_REF]. Several papers are available in the literature related to methods for the functional self-test of processors, but only few of them refer to the test of Very Long Instruction Word (VLIW) processors [START_REF] Sabena | A new SBST algorithm for testing the register file of VLIW processors[END_REF][13][14] [START_REF] Pillai | Detecting VLIW hard errors cost-effectively through a software-based approach[END_REF].

In [START_REF] Sabena | A new SBST algorithm for testing the register file of VLIW processors[END_REF] we proposed a new SBST algorithm oriented to the test of the Register File of a generic VLIW processor; that paper highlights the particular structure of the register file belonging to a VLIW processor, that presents a particular structure since it is shared by all the computational domains of the processor; in particular, the proposed algorithm is able to efficiently test the complex cross-bar switch embedded into the component. Another technique able to obtain a good diagnostic resolution with a low hardware overhead is proposed in [START_REF] Ulbricht | A new hierarchical built-in selftest with on-chip diagnosis for VLIW processors[END_REF]; this technique combines scan and SBST and it is oriented to the test of VLIW processors. The specific characteristic of that approach is the ability to detect faults inside the processor functional units, obtained by loading the same test patterns directly to the test registers of all the computational domains. The proper functionality of each domain is tested by comparing the test response of all domains, which should be the same than in the fault-free case. This solution involves a hardware overhead of about 6% and requires that the processor run in selftest mode.

Similar to test approaches, several Software-Based Diagnosis (SBD) methods applied to processors have been recently developed. In [START_REF] Bernardi | An Effective Technique for Minimizing the Cost of Processor Software-Based Diagnosis in SoCs[END_REF] a new cost-effective approach is presented: the approach is based on the automatic generation of a diagnostic test set using an existing post-production test set; the authors propose to improve that set using an evolutionary method. In [START_REF] Ulbricht | A New Hierarchical Built-In Self-Test with On-Chip Diagnosis for VLIW Processors[END_REF] the authors present a new diagnostic method for VLIW processors, based on scan-based BIST and SBST, aimed at a good diagnostic resolution with low hardware overhead. Software-based BIST is introduced for a fast diagnosis of the Computational Domains of the processor. This is an initial work in the field and it is based on the use of several existing self-test techniques; moreover, it is based on a specific VLIW processor and requires the introduction of several hardware test module in the considered processor.

4

The Proposed Method 2); hereafter, the detailed description of each of these steps will be provided. The only two requirements for the global generation flow are the manifest of the VLIW processor under test, containing all the features of the processor itself, and a library containing a set of programs able to autonomously test the different modules within the processor. The library is a collection of generic SBST programs taken from the literature [START_REF] Sabena | A new SBST algorithm for testing the register file of VLIW processors[END_REF][12] [START_REF] Gizopoulos | Systematic software-based self-test for pipelined processors[END_REF][17] [START_REF] Kranitis | Instruction-based self-testing of processor cores[END_REF]: it contains some functional test code able to test the most relevant Functional Units of a generic VLIW processor. The codes stored into the library are purely functional (i.e., do not require any Design for Testability feature) and are completely independent of any physical implementation of the Functional Unit they refer; these codes are described with a pseudo-code based on C language. The mapping process of these codes to the specific architecture under test is performed by the second step of the proposed method (i.e., the Customization step).

Fragmentation

The goal of the Fragmentation phase is the minimization of the number of test operations in order to generate optimized and efficient test programs. Two main tasks are performed by the Fragmentation phase: the first is the selection from the library of the test programs needed to test the VLIW processor under test, ignoring those which refer to Functional Units that are not belonging to the processor itself. The second task performed by this step is the fragmentation of each selected test program into a set of smaller pieces of code, named Fragments, containing few test operations and the other instructions needed to perform an independent test. The generation of a fragment is done by building it around a single instruction, and includes some preliminary instructions required to correctly perform it and to forward the results into observable locations [2][19]; the description of a Fragment is performed through some architecture-independent code. On the other hand, a test program is typically composed of a set of test operations enclosed in a loop; a series of short test programs are

Fragmentation

Customization

Fragments Library Library Custom Fragments Library

Fault Simulation

Selection

Scheduling

VLIW Test program

VLIW manifest

Step A

Step B

Step C.1

Classification

Test Flow Diagnosis Flow

Equivalence Check

Diagnosis Evaluation

Step C.2 generated by simply separating the test operations using the Loop Unrolling technique, as shown into the pseudo-code of Fig. 3.

The code is then optimized by executing the Fragmentation phase, which exploits the fact that a VLIW processor is composed of parallel computational domains that execute several operations in parallel, as described in Section 2. Due to this feature, when a SBST program is executed with the purpose of testing a selected unit, at the same time several operations can also be executed on other parallel units. In Fig. 4 an example of this concept is shown, where it is possible to notice that by applying the SBST program for the test of the VLIW register file [START_REF] Sabena | A new SBST algorithm for testing the register file of VLIW processors[END_REF] several faults related to the Functional Units (e.g., the adders and the MEM unit) are also covered. The main idea behind test program fragmentation is to divide the original programs in atomic test units in order to effectively evaluate each one of them; multiple fault coverage is therefore avoided and the test code can be optimized in terms of test time and used resources. Once the Fragmentation phase is completed, a new library called Fragments Library is obtained, that contains the set of architecture-independent Fragments.

Customization

The translation of the generic architecture-independent test programs into the VLIW code is managed by the Customization step, which uses the Instruction Set Architecture (ISA) of the considered processor. In detail, starting from the VLIW manifest and from the Fragments Library, the method translates each generic Fragment into a Custom Fragment that can be executed by the processors under test. A Custom Fragment is defined as a set of instructions related to the ISA of the processor under test that performs several operations in order to test the addressed Functional Unit. In Table 1 an example of the Customization process is reported, where the code of a Fragment before and after the Customization phase appears. The example is based on a multiplication instruction, and the produced result is saved into the memory. As the reader can notice, at the beginning the code is a generic ISA-independent code, while after the Customization step, a VLIW code is generated, exploiting the ρ-VEX processor ISA [10][11].

Table 1. Example of the translation performed by the customizer. ---------------------------The Customization phase performs two relevant tasks: the definition of the resources needed to execute the code (such as the memory area required and the registers) and the introduction of the information, inside the code, that assign the execution of an instruction to a defined VLIW Computational Domain. In Table 1, it is reported an example of this translation, where CDx is the Computational Domain in charge of executing the addressed instruction.

Before

The translation of each Fragment is performed independently from the others; furthermore, one architecture-independent Fragment can be translated into several architecture-dependent Fragments, following the features listed in the VLIW manifest, such as the type of functional units contained in each Computational Domain: for example, if in the considered VLIW processor there are 4 adder units, one for each of the 4 Computational Domains, the generic Fragment related to the test of an adder is translated into 4 architecture-dependent Fragments, one for each adder unit embedded into the Computational Domains. When the Customization phase is terminated, each architecture-dependent Fragment is fault simulated in order to compute a detailed list of faults covered by the specific test program considering all the resources of the VLIW processor. Finally, a library called Custom Fragments Library is obtained: it contains all the architecture-dependent Fragments used to test the processor under test and the list of faults covered by each of them. As shown in Fig. 2, the fault lists associated to each Custom Fragment are also used for the diagnosis flow, as we will explain in Section 4.4.

Selection and Scheduling

During this phase two important processes are performed: the selection of the Custom Fragments, according to the objective to be achieved, and the merge of these in order to obtain a compact and efficient test program.

Considering the Selection step, the Custom Fragments are selected by an algorithm which implements two alternative rules depending on the user requirements. The first rule is based on the selection of the minimum number of Custom Fragments that allow to reach the maximum coverage with respect to all resources of the processor under test. In this way several Custom Fragments are not selected since the faults covered by these Fragments are already covered by other fragments previously selected. The pseudo-code of this algorithm is shown in Fig. 5. The second rule is based on optimizing the number of resources used by the selected Custom Fragments. The maximal number of usable resources, in terms of registers and memory words, can be specified by the user. On the basis of these constraints, the algorithm selects the Custom Fragments that allow to reach the maximum coverage without using more resources than those specified. In this way the method is able to generate test programs depending on the final requirements: for example, if the final goal is to generate test programs for on-line testing, with the use of this algorithm we are able to generate test codes that exploit only a limited set of registers and memory words.

FL = Fault

At the end of the Selection phase, the selected Custom Fragments enter the Scheduling phase: this process is responsible for the integration of the Custom Fragments, in order to obtain an optimized and efficient final test program. To reach this goal the scheduler optimizes and merges the codes contained into the Custom Fragments exploiting the VLIW features; in particular, it compacts the test programs aiming at maximizing the ILP of the processor. To perform the merge operation two techniques are defined and adopted; considering two or more Custom Fragments, the former is based on the exploitation of the common input pattern belonging to different instructions: in this case it is not required to define two instances of the same input data to perform the test instructions; an example of this operations is shown in Table 2, where two Custom Fragments, related to the test of the adder units embedded into the Computational Domain 0 and 1, are merged into a single test program. In this way the ILP is better exploited and the number of macro-instructions required is less than the sum of the macro-instructions of the two Fragments. The latter technique is based on the maximization of the ILP of the VLIW architecture: starting from the code of the selected Custom Fragments, the macro-instructions of these codes are merged together in order to maximize the parallel operations executed by the code. --------------------- ;----------------------The goal of this scheduling technique is to generate the macro-instructions of the final test program, thus reducing the whole test time. Three analysis steps are required to acquire the necessary information with respect to each Custom Fragment: the resources required by the code, such as the registers, the memory words and the Func-tional Units exploited; the temporal characteristics, defined as the number of clock cycles where the resources mentioned above are employed in the execution of the code; finally, the data dependences between the instructions belonging to the Custom Fragments. These pieces of information are used to create the final test program, according to the features of the VLIW processor described in the VLIW manifest. In order to do this, the scheduler uses three structures: the first is an activity frame schedule that is used to schedule the execution of the Custom Fragments into the Computational Domains: an example of this is reported in Fig. 6, where the chart representation of the activity frame schedule of the code listed in Table 2 is reported, consisting of two Custom Fragments, called A and B, each composed of three macroinstructions called A-1, A-2, A-3 and B-1, B-2, B-3, respectively. The second structure needed to create the final test program is a graph structure, where the dependences between the instructions composing the program are saved; in Fig. 7 is reported the graph structure related to the simple example shown in Table 2. Finally, the last structure is a graph containing the information about the resources, such as registers and memory word, used by the final test program for each clock cycle. At the end of this step, the final test program is generated.

Table 2. Example of the optimization operations performed by the scheduler

Custom

Classification and Equivalence Check

In some situations, diagnosis is required, which means that the goal becomes the identification of the fault existing in the unit under test. For example, diagnosis is crucial in the ramp-up phase of a new product, when the yield of the production process is expected to grow thanks to the tuning of the process (which requires knowing where the faults are) [START_REF] Bernardi | An Effective Technique for the Automatic Generation of Diagnosis-Oriented Programs for Processor Cores[END_REF]. Another typical scenario where diagnosis is crucial is when sys-

Resources clock cycle CD 0 CD 1 A -1 A -2 A -3 B -1 B -2 B -3 Custom Fragment A Custom Fragment B B -1 A -2 B -2 B -3 A -3 1 2 3 4 B-1 A-2 B-2 A-3 B-3
tem reconfiguration can be performed after a fault is detected, e.g., thanks to the adoption of a programmable architecture: in this case diagnosis is crucial to identify (once a fault is detected during the operational phase) the partition containing the fault, so that the system can be reconfigured and the partition can be substituted by a fault-free one [START_REF] Koester | Design Optimizations for Tiled Partially Reconfigurable Systems[END_REF].

Given the importance of diagnosis, we performed a preliminary analysis about the diagnostic power of the test programs generated by our method, and we made some considerations aimed at improving their diagnosis capabilities.

First of all, we will define the notation to be used and the steps of the diagnosis method; then, we will report some experimental figures (in Section 5.2) about the diagnostic capabilities of the test programs generated by the proposed method.

Notation. Let us call F = {f 0 , f 1 , …, f n-1 } the set of n faults that can affect the Unit Under Test (UUT). Each of these faults causes the UUT to produce a given output behavior b when a given sequence of input stimuli is applied; let b i denote the output behavior produced by fault f i , and b g the output behavior of the fault-free circuit. Clearly, b i = b g for all undetected faults f i . In the literature (and in practice) the output behavior can be observed (for the purpose of diagnosis) resorting to two different criteria:  Criterion #1: the output behavior of a fault is simply the sequence of time instants in which the fault is detected. Therefore, according to this criterion b i = b j iff the two faults f i and f j are detected in the same time instants.  Criterion #2: the output behavior of a fault is the sequence of output values produced by the fault. Therefore, according to this criterion b i = b j iff the two faults f i and f j always produce the same output values. For the purpose of this paper we will consider a criterion which is a mix of criterion #1 and criterion #2. In particular, we will classify faults according to an output behavior corresponding to the set of values produced by the program at the end of its execution. Therefore, according to this criterion b i = b j iff the two faults f i and f j produce the same output values in memory at the end of their execution.

A given pair of faults (f i , f j ) is said to be distinguished by a given sequence of input stimuli I iff b i  b j . Otherwise, they are said to be equivalent wrt I. All faults that are equivalent wrt to a give sequence of input stimuli I are said to belong to the same Equivalence Class wrt I. A detected fault f i is said to be fully diagnosed by a sequence of input stimuli I iff any couple of faults (f i , f j ) including f i is distinguished by I. Since two faults f i , f j can never be distinguished if they are functionally equivalent, the number of fully diagnosed faults in a circuit is typically rather low.

Several possible metrics can be adopted to measure the diagnostic capabilities of a sequence of input stimuli I [START_REF] Ryan | Fault dictionary compression and equivalence class computation for sequential circuits[END_REF]. A popular one is the so-called diagnostic resolution, or DR(I), which corresponds to the fraction of all pairs of detected faults that are distinguished by I.

When diagnosis is used in reconfigurable system for identifying the partition including the fault, the precision required is lower: in fact, the final goal in this case is to be able to distinguish all pairs of faults belonging to different partitions, while distinguishing pairs of faults belonging to the same partitions is not of interest. Hence, in this case a different definition of the diagnostic resolution can be introduced, based on a given partition of the circuit elements among P partitions. Assuming that the generic fault f i is associated to the partition p i , we will only consider those pairs of faults (f i , f j ) such that p i  p j and define the partition-oriented diagnostic resolution of a given sequence of input stimuli I, or PRDR(I), as the fraction of all pairs of detected faults belonging to different partitions that are distinguished by I.

Method. Considering the Diagnosis flow, shown in Fig. 2 Step C.2, there are two main steps necessary to acquire the diagnostic data.

First of all the fault lists associated to each Custom Fragment, and generated through fault simulation (Fig 2 , Step B) are analyzed and compared: the goals of this analysis are (1) the classification of each fault, belonging to the VLIW processor under test, in the class of distinguished and equivalent faults, respectively, and (2) the creation of the equivalence classes, according to the notation described in the previous paragraph.

The second step is the analysis and the classification of the equivalence classes; for each of them, the classification is based on the number of partitions that have at least one fault in the considered equivalence class; the composition of the partition defines the granularity of the diagnosis and it is managed by the final user, according to the chosen diagnosis goal.

At the end of these two steps, using the obtained data and given a fault in the considered VLIW processor, we will be able to either uniquely identify it (if the fault is distinguished), or to identify the partition (one or more) containing the fault itself and the equivalent faults (if the fault has one or more equivalent).

Experimental Results

In this section, we present the experimental results, both for the optimized generation of the SBST program and for the diagnosis evaluation; the ρ-VEX VLIW processor has been used as a case study (Fig. 8). The ρ-VEX is a VLIW processor released by researchers from Delft University of Technology [START_REF] Wong | Dynamically reconfigurable register file for a softcore VLIW processor[END_REF] [START_REF] Wong | ρ-VEX: a reconfigurable and extensible softcore VLIW processor[END_REF]. Among its main features, the most important advantage is the possibility of reconfiguring the pipeline according to the user need. The pipeline, in the standard configuration, is composed of four stages: fetch, decode, execute and write-back. Following the VLIW architecture principles, the decode, execute and write-back stages are divided into four Computational Domains (CD). The fetch unit is in charge of fetching a VLIW macro-instruction from the attached instruction memory; then, it splits the considered macro-instruction into several (according to the processor configuration) micro-instructions; finally, these are passed in parallel to the decode unit. In the decoding stage two main tasks are executed: firstly, the operations are performed, and secondly the registers used as operands are fetched from the general purpose register file (the GR module of Fig. 8) and from the branch management register file (the BR module of Fig. 8). The micro-operations are then forwarded to the parallel execution units, that in this case are ALUs (1 ALU for each CD) and MULs (2 MULS, embedded in the second and in the third CD). Fig. 8. The ρ-VEX VLIW processor [START_REF] Wong | Dynamically reconfigurable register file for a softcore VLIW processor[END_REF] [START_REF] Wong | ρ-VEX: a reconfigurable and extensible softcore VLIW processor[END_REF].

In order to perform the stuck-at fault simulation experiments, we synthesized and implemented the ρ-VEX processor using a standard ASIC gate library. In total the number of faults is 387,290. The assembly code generated following the described method has been inserted into the instruction memory; then, a fault simulation experiment has been performed. Moreover, we wrote a prototypical tool (composed of about 3K lines of C++ code) implementing the proposed methods.

First of all, we have selected 6 SBST programs [START_REF] Sabena | A new SBST algorithm for testing the register file of VLIW processors[END_REF][12] [START_REF] Gizopoulos | Systematic software-based self-test for pipelined processors[END_REF][17] [START_REF] Kranitis | Instruction-based self-testing of processor cores[END_REF] from the literature for testing the Functional Units embedded in the processor: each of them has been encoded in architecture-independent pseudo-code and has been inserted in the starting library. At the end of the fragmentation step we obtained a Fragments Library composed of 520 architecture-independent Fragments, while at the end of the Customization step the Custom Fragments Library was composed of 989 Custom Fragments.

Optimized SBST Program Generation Results

Using the technique for the maximum coverage with the minimum number of Fragments, 768 Custom Fragments have been selected and subjected to the scheduling step. plied using the loop-unrolling technique, as it is common for any VLIW application. In Table 3 we compare the obtained results.

As the reader can notice, while the coverage remains at the 98%, the number of clock cycles and the size of the test program generated with the proposed method decreased significantly. This is due to two causes: the former is that not all the Custom Fragments are chosen in the selection step; in fact the maximum coverage is reached with about 78% of the Custom Fragments. This comes from the fact that some fragments are aimed at detecting faults in some unit, which were already covered by Fragments targeted at other units. The latter is related to the scheduling step, that optimizes the code compacting the instructions, exploiting the VLIW features, and parallelizing as much as possible the execution of the Custom Fragments; consequently, the amount of clock cycles required by the final test program, is about 54% less than in the test program obtained using previously developed test programs without any selection or scheduling improvements.

It is also worth mentioning that the proposed method was able to reduce by about 58% the size of the test code. In Table 4 the achieved coverage for the relevant units of the ρ-VEX processor are reported.

Diagnosis Evaluation Results

First of all we wrote a C++ program able to compare the fault lists generated by the Fault Simulation step (Section 4.2); the goal of this program is the detection of the number of distinguished faults and the classification of the undistinguished faults, i.e., the equivalent faults, in two categories: the first is composed of the faults which are equivalent and belonging to the same partition, while the second is composed of the faults belonging to different partitions. For this purpose, we divided the ρ-VEX processor in 10 partitions: the fetch unit, the decode unit, the general-purpose register file, the branch-management register file, the write-back unit, and one for each Computational Domains (i.e., 4) in which the functional units are embedded. Then, we run this program using two different sets of fault lists: the first contains only the fault lists associated to the Custom Fragments selected by the Selection step (Fig. 2, Step C.1) of the optimized generation of the SBST program, which are 78% of the total; the second set, instead, contains the fault lists of all the Custom Fragments generated by the Customization step. In Table 5 the results of these two experiments are reported.

As it is possible to notice, the set of all fault lists (set 2) allows to increment the number of distinguished faults and the number of the equivalent faults belonging to the same partition. Consequently, considering the results of Table 5, given a fault in the ρ-VEX processor, in about 82% of the cases we are able to identify the partition affected by the fault itself.

In Table 6 the evaluation of the Equivalence Classes, generated when all the fault lists of the all Custom Fragments are considered (fault lists set 2), is shown; the purpose of this evaluation is the classification of each equivalence class, based on the number of partitions with at least one fault in the considered equivalence class. As reported in Table 6, about 93% of the equivalence classes are composed of faults belonging to the same partition. In the other cases, as reported in the graph of Fig. 9, most of the classes are composed of equivalent faults belonging to two (54.52%) or three (38.81%) different partitions.

Conclusions and Future Work

In this chapter we presented the first method able to automatically generate optimized Software-Based Self-Test programs for VLIW processors. The obtained results, with respect to the selected case study, clearly demonstrate the efficiency of our method, that allows to reduce significantly both the number of clock cycles and the required memory resources with respect to the plain application of previous methods. Moreover, it is also possible to exploit the proposed method to obtain a set of small SBST programs useful for the diagnosis of the considered VLIW processor.

As future work we plan to better evaluate the performance of the proposed solution with the use of another VLIW model with different Functional Units; moreover, we plan to generate small optimized SBST programs that can be specifically used for on-line testing and able to improve the diagnosis capabilities. Equivalence Class Evaluation

Fig. 1 .F

 1 Fig. 1. Architectural differences between a superscalar and a VLIW CPU.

Fig. 2 .

 2 Fig. 2. The flow of the proposed test and diagnosis method.

1 .Fig. 3 .

 13 Fig. 3. The pseudo-code of the Fragmentation phase.

Fig. 4 .

 4 Fig. 4. The Fault Coverage of the test program for the Register File with respect to faults in the other modules of the processor.

  Customization R = mul (All 0's, All 0's); Store(R , memory); After Customization ;;----Macro-instruction 1----CD0 : mov R1 = 0; CD1 : mov R2 = 0; ;;----Macro-instruction 2----CD0 : mul R3 = R1, R2; ;;----Macro-instruction 3----CD0 : stw 4[R7] = R3;//R7 is the stack pointer ;;-

Fig. 5 .

 5 Fig. 5. The pseudo-code of the algorithm for the selection of the Custom Fragments.

  -Macro-instruction A1 CD0 : mov R1 = 0; CD1 : mov R2 = 0; ;;--Macro-instruction A2 CD0 : add R8 = R1, R2; ;;--Macro-instruction A3 CD0 : stw 0[R1] = R8; ;;----------------------;;--Macro-instruction B1 CD0 : mov R1 = 0; CD1 : mov R2 = 0; ;;--Macro-instruction B2 CD1 : add R9 = R1, R2; ;;--Macro-instruction B3 CD0 : stw 0[R1] = R9; ;;-

Fig. 6 .

 6 Fig. 6. The chart representation of the activity frame schedule.

Fig. 7 .

 7 Fig. 7. The graph structure for the instruction dependence.

Fig. 9 .

 9 Fig. 9. The classification of the equivalent classes calculated using all the available faults lists.

  -

	Final Test Program F
	;;--Macro-instruction F1
	CD0 : mov R1 = 0;
	CD1 : mov R2 = 0;
	;;--Macro-instruction F2
	CD0 : add R8 = R1, R2; //tests the adder of CD0
	CD1 : add R9 = R1, R2; //tests the adder of CD1
	;;--Macro-instruction F3
	CD0 : stw 0[R7] = R8; //R7 is the stack pointer
	;;--Macro-instruction F4
	CD0 : stw 4[R7] = R9; //R7 is the stack pointer
	;

  At the end, we obtained the final test program for the test of the ρ-VEX processor: the generation time was approximately 40 hours, of which about 95% used for the fault simulation of the Custom Fragment. Computational time has been evaluated on a workstation with an Intel Xeon Processor E5450. We compared the test program generated by our approach with a test program consisting in several literature-based test programs simply queued in a unique test program, without performing any selection or scheduling steps, therefore adopting a realistic test estimation of what can be achieved with previously developed test algorithms without any optimization method. In order to fairly evaluate the two solutions, the original test programs have been ap-

		PC	GR	CTRL
	Instruction Memory	Fetch	Decode	A Execute A A M A M	Writeback	Data Memory
			BR	MEM
		ρ-VEX processor

Table 3 .

 3 Optimized SBST program generation: obtained results.

	Test	Clock	Fault	Size
	Program	cycle [#]	Coverage	[KB]
	Original Test Programs	18,540	98.2%	3,894
	Proposed method	8,447	98.2%	1,612

Table 4 .

 4 Details of the achieved fault coverage.

	ρ-VEX Components	Faults [#]	Fault coverage
	Fetch		2,156	99.2%
	Decode		269,196	98.1%
		4 ALU	75,554	98.3%
	Execute	2 MUL	37,244	98.6%
		MEM	1,730	97.2%
	Writeback		1,420	98.1%
	Total	387,290	98.2%

Table 5 .

 5 Faults classification: diagnosis point of view.

	Faults lists set	Distinguished Faults	SAME partition	Equivalent Faults DIFFERENT partitions	TOTAL
	1 -Optimized Test	1.13%	63.29%	35.59%	98.87%
	2 -All	2.78%	79.15%	18.07%	97.22%

Table 6 .

 6 Equivalence classes evaluation.

	Partition [#]	E.C. [#] E.C. [%] Faults Category
	1	14,319	92.90 % Equivalent -SAME partition
	2	597	54.52 %
	3	425	38.81 %
	4	42	3.84 %
	5 6 7	21 9 0	1.92 % 0.82 % 0.00 %	Equivalent -DIFFERENT partition
	8	1	0.09 %
	9	0	0.00 %
	10	0	0.00 %

This work has been partially supported by the European Commission through the LoRelei project (PIRES-GA-2011-29521).