This paper presents an improved hardware structure for the computation of the Whirlpool hash function. By merging the round key computation with the data compression and by using embedded memories to perform part of the Galois Field (2s) multiplication, a core can be implemented in just 43% of the area of the best current related art while achieving a 12% higher throughput. The proposed core improves the Throughput per Slice compared to the state of the art by 160%, achieving a throughput of 5.47 Gbit/s with 2110 slices and 32 BRAMs on a VIRTEX II Pro FPGA. Results for a real application are also presented by considering a polymorphic computational approach.

Extended subwords and the matrix register file (MRF) are two micro architectural techniques that address some of the limitations of existing SIMD architectures. Extended subwords are wider than the data stored in memory. Specifically, for every byte of data stored in memory, there are four extra bits in the media register file. This avoids the need for data-type conversion instructions. The MRF is a register file organization that provides both conventional row-wise, as well as column-wise, access to the register file. In other words, it allows to view the register file as a matrix in which corresponding subwords in different registers corresponds to a column of the matrix. It was introduced to accelerate matrix transposition which is a very common operation in multimedia applications. In this paper, we show that the MRF is very versatile, since it can also be used for other permutations than matrix transposition. Specifically, it is shown how it can be used to provide efficient access to strided data, as is needed in, e.g., color space conversion. Furthermore, it is shown that special-purpose instructions (SPIs), such as the sum-of-absolute differences (SAD) instruction, have limited usefulness when extended subwords and a few general SIMD instructions that we propose are supported, for the following reasons. First, when extended subwords are supported, the SAD instruction provides only a relatively small performance improvement. Second, the SAD instruction processes 8-bit subwords only, which is not sufficient for quarter-pixel resolution nor for cost functions used in image and video retrieval. Results obtained by extending the SimpleScalar toolset show that the proposed techniques provide a speedup of up to 3.00 over the MMX architecture. The results also show that using, at most, 13 extra media registers yields an additional performance improvement ranging from 1.38 to 1.57.

The 2-D Discrete Wavelet Transform (DWT) consumes up to 68% of the JPEG2000 encoding time. In this paper, we develop efficient implementations of this important kernel on general-purpose processors (GPPs), in particular the Pentium 4 (P4). Efficient implementations of the 2-D DWT on the P4 must address three issues. First, the P4 suffers from a problem known as 64K aliasing, which can degrade performance by an order of magnitude. We propose two techniques to avoid 64K aliasing which improve performance by a factor of up to 4.20. Second, a straightforward implementation of vertical filtering incurs many cache misses. Cache performance can be improved by applying loop interchange, but there will still be many conflict misses if the filter length exceeds the cache associativity. Two methods are proposed to reduce the number of conflict misses which provide an additional performance improvement of up to 1.24. To show that these methods are general, results for the P3 and Opteron are also provided. Third, efficient implementations of the 2-D DWT must exploit the SIMD instructions supported by most GPPs, including the P4, and we present MMX and SSE implementations of horizontal and vertical filtering which provide a maximum speedup of 3.39 and 6.72, respectively.

Up to 53% of the time spent on testing current Intel microprocessors is needed to test on-chip caches, due to the high complexity of memory tests and to the large amount of transistors dedicated to such memories. This paper discusses the methodology used to develop effective and efficient cache tests, and the way it is implemented to optimize the test set used at Intel to test their 512-kB caches manufactured in a 0.13- mum technology. An example is shown where a maximal test set of 15 tests with a corresponding maximum test time of 160.942 ms/chip is optimized to only six tests that require a test time of only 30.498 ms/chip.

This paper presents a new set of techniques for hardware implementations of secure hash algorithm (SHA) hash functions. These techniques consist mostly in operation rescheduling and hardware reutilization, therefore, significantly decreasing the critical path and required area. Throughputs from 1.3 Gbit/s to 1.8 Gbit/s were obtained for the SHA implementations on a Xilinx VIRTEX II Pro. Compared to commercial cores and previously published research, these figures correspond to an improvement in throughput/slice in the range of 29% to 59% for SHA-1 and 54% to 100% for SHA-2. Experimental results on hybrid hardware/software implementations of the SHA cores, have shown speedups up to 150 times for the proposed cores, compared to pure software implementations.

In this paper, we consider hardware-based scanning and analyzing packets payload in order to detect hazardous contents. We present two pattern matching techniques to compare incoming packets against intrusion detection search patterns. The first approach, decoded partial CAM (DpCAM), predecodes incoming characters, aligns the decoded data, and performs logicalandon them to produce the match signal for each pattern. The second approach, perfect hashing memory (PHmem), uses perfect hashing to determine a unique memory location that contains the search pattern and a comparison between incoming data and memory output to determine the match. Both techniques are well suited for reconfigurable logic and match about 2200 intrusion detection patterns using a single Virtex2 field-programmable gate-array device. We show that DpCAM achieves a throughput between 2 and 8 Gb/s requiring 0.58–2.57 logic cells per search character. On the other hand, PHmem designs can support 2–5.7 Gb/s using a few tens of block RAMs (630–1404 kb) and only 0.28–0.65 logic cells per character. We evaluate both approaches in terms of performance and area cost and analyze their efficiency, scalability, and tradeoffs. Finally, we show that our designs achieve at least 30% higher efficiency compared to previous work, measured in throughput per area required per search character.

In this paper we present a novel adder/subtracter arithmetic unit that combines binary and binary code decimal (BCD) operations. The proposed unit uses effective addition/subtraction operations on unsigned, sign-magnitude, and various complement representations. Our design overcomes the limitations of previously reported approaches that produce some of the results in complement representation when operating on sign-magnitude numbers. The proposal can be implemented in ASIC as a run time configurable unit as well as in reconfigurable technology in form of a run-time reconfigurable engine. When reconfigurable technology is considered, a preliminary estimation indicates that 40 % of the hardware resources are shared by the different operations. This makes the proposed unit highly suitable for reconfigurable platforms with partial reconfiguration support. The proposed design together with some classical adder organizations were compared after synthesis targeting 4vfx60ff672-12 Xilinx Virtex 4 FPGA. Our design achieves a throughput of 82.6 MOPS with almost equivalent area-time product when compared to the other proposals.

We present a design of a customized crossbar scheduler for on-chip networks. The proposed scheduler arbitrates on-demand interconnects, where physical topologies are identical to logical topologies for given applications. Considering conventional fully parallel and sequential schedulers as reference designs, a comparative performance analysis is conducted. The hardware scheduler module is implemented with parameterized arbiter arrays. Experiments with practical applications show that the crossbar network with our custom scheduler realizes on-demand traffic patterns, occupies on average 52% less area, and maintains higher performance, compared to the crossbar network with a fully parallel scheduler. Additionally, our custom scheduler performs significantly better than the sequential scheduler with moderate area overheads for small-sized tokens communicated over large networks.

Existing SIMD extensions cannot efficiently vectorize the histogram function due to memory collisions. We propose two techniques to avoid this problem. In the first, a hierarchical structure of three levels is proposed. In order to provide n-way parallelism, auxiliary arrays that have n and n/2 subarrays are used in the first and second level, respectively. The last level has the primary histogram array. Indirect SIMD load and store instructions are designed in order to access different elements of different subarrays. The different subarrays in the lower levels are merged and finally at the end, the calculated results are stored in the primary histogram array. In the second method, parallel comparators are used in order to count the number of subwords within a media register that are the same. Thereafter, these numbers are added to the values of the histogram array simultaneously. Experimental results obtained by extending the SimpleScalar toolset show that proposed techniques improve the performance compared to the fastest scalar version by a factor of 7.37 and 5.52, respectively.

The aim of the hArtes project is to facilitate and automate the rapid design and development of heterogeneous embedded systems, targeting a combination of a general purpose embedded processor, digital signal processing and reconfigurable hardware. In this paper, we evaluate three tools from the hArtes toolchain supporting profiling, compilation, and HDL generation. These tools facilitate the HW/SW partitioning, co-design, co-verification, and co-execution of demanding embedded applications. The described tools are provided by the DelftWorkBench framework1. Experimental results on MJPEG and G721 encoder application case studies suggest overall performance improvement of 228% and 36% respectively.

An important step in Heterogeneous System Development is Hardware/Software Partitioning. This process involves exploring a huge design space. By using profiling to select hot-spots and estimate area and delay we can prune the design space considerably. We present a Quantitative Model that makes early predictions to prune the design space and support the partitioning process. The model is based on Software Complexity Metrics, which capture important aspects of functions as control intensity, data intensity, and code size. To remedy interdependence among software metrics, we performed a Principal Component Analysis. The hardware characteristics were determined by automatically generating VHDL from C using the DWARV C-to-VHDL compiler. Linear regression on these data generated our model. The model error differs per hardware characteristic. We show that for flip-flops the mean error is 69%. In conclusion, our quantitative model makes fast and sufficiently accurate area predictions in support of early Hardware/Software Partitioning.

Recently, a dedicated hardware accelerator was proposed that works in conjunction with caches found next to modern-day microprocessors, to speedup the commonly utilized memcpy operation. The main assumption of the proposal was that the to-be-memcpy-ed data has to reside inside the cache, which is not always valid. In this paper, we present a dedicated load/store unit and its implementation which cooperates with the previously proposed memcpy hardware accelerator and cache to ensure that data becomes available in the cache. Experimental results, using synthetic benchmarks, show that the load/store unit in conjunction with the memcpy hardware accelerator is capable of reducing the memcpy latencies by 85% (when the data is not present in the cache) compared to a highly optimized, hand-coded in assembly software solution.

In this paper, we present the DWARV C-to-VHDL generation toolset. The toolset provides support for broad range of application domains. It exploits the operation parallelism, available in the algorithms. Our designs are generated with a view of actual hardware/software co-execution on a real hardware platform. The carried experiments on the MOLEN polymorphic processor prototype suggest overall application speedups between 1.4x and 6.8x, corresponding to 13% to 94% of the theoretically achievable maximums, constituted by Amdahl's law.

The instruction-set extension problem has been one of the major topics in the last decade and it consists of the addition of a set of new complex instructions to a given instruction-set. This problem in its general formulation requires an exhaustive search of the design space to identify the candidate instructions. A tradeoff between complexity and quality of the solution can be achieved limiting this search to implementable instructions. In this paper we propose a linear complexity algorithm for the generation of convex multiple input multiple output (MIMO) instructions of variable size based on the notion of spiral. Convex implementable MIMO clusters of instructions are identified by means of a spiral search through the levels of a graph. These new instructions can be directly selected or combined for more complex instruction-set extensions. An important feature of our algorithm is that it is neither restricted to basic-block level nor it imposes any limitation on the number of the newly instructions nor on the number of the inputs/outputs of these instructions.

Loops are an important source of performance improvement, for which there exists a large number of compiler based optimizations. Few optimizations assume that the loop will be fully mapped on hardware. In this paper, we discuss a loop transformation called recursive variable expansion, which can be efficiently implemented in hardware. It removes all the data dependencies from the program and then the parallelism is only bounded by the amount of resources one has. To show the performance improvement and the utilization of resources, we have chosen four kernels from widely used applications (FIR, DCT, Sobel edge detection algorithm and matrix multiplication). The hardware implementation of these kernels proved to be 1.5 to 77 times faster (depending on application) than the code compiled and run on PowerPC.

The current system design of mobile ad hoc networks (MANET), derived from their traditional fixed counterparts, cannot fully meet the requirements inherent to the dynamic nature of such networks. Cross-layer (CL) designs, a modification of the classic protocol stack, are envisioned as a solution for this problem. Many CL design approaches are proposed, each for a different optimization purpose. Mobile terminals require a variety of optimizations that can be provided only by using different CL designs. Consequently, the coexistence and interaction of such designs needs attention. The lack of common interface and infrastructure among different CL designs, however, makes their interaction a significant problem. The proposed common interaction infrastructure is able to compensate for the negative effects introduced by particular CL design by using runtime information from all CL implementations involved in the system. This paper first presents an analysis of the weaknesses of standalone CL designs. Furthermore, this paper introduces a novel architecture to ensure optimal interaction of multiple CL designs according to different QoS requirements. A piggybacked signaling protocol using XML based internal messaging format is introduced. The proposed architecture and three CL designs were simulated for various network scenarios and compared in terms of delay and network efficiency (using the throughput percentage). The results show that the performance with the interaction framework is averagely within 3% to that of the best individual case and maybe up to 4.5% better. In addition, the QoS requirements are always respected.

Reconfigurable computing (RC) systems, coupling general purpose processor with reconfigurable components, offer a lot of advantages. Nevertheless, currently a designer needs both in-depth software and hardware design knowledge to develop applications for such platforms. The automated hardware generation addresses this problem. However, the success of such tools remains marginal. This paper discusses the reasons for the lack of success. It presents a quantitative and qualitative comparison of three hardware generators using the following criteria: quality of the hardware model, the supported HLL constructs, and the level of automation.

The 2D DWT consists of two 1D DWT in both directions: horizontal filtering processes the rows followed by vertical filtering processes the columns. It is well known that a straightforward implementation of the vertical filtering shows quite different performance with various working set sizes. The only reasonable explanation for this has to be the access behavior of the cache memory. As known, vertical filtering has mapping conflicts in the cache with a working set size that is power of two. However, it is not clear how this conflict forms and whether cache problems exist with other data sizes. Such knowledge is the base for efficient code optimization. In order to acquire this knowledge and to achieve more accurate optimization potentials, we apply a cache visualization tool to examine the runtime cache activities of the vertical implementation. We find that besides mapping conflicts, vertical filtering also shows a large number of capacity misses. More specifically, the visualization tool allows us to detect the parameters related to the strategies. This guarantees the feasibility of the optimization. Our initial experimental results on several different architectures show an up to 215% gain in execution time compared to an already optimized baseline implementation.

In this paper, we describe the compiler developed to target the Molen reconfigurable processor and programming paradigm. The compiler automatically generates optimized binary code for C applications, based on pragma annotation of the code executed on the reconfigurable hardware. For the IBM PowerPC 405 processor included in the Virtex II Pro platform FPGA, we implemented code generation, register, and stack frame allocation following the PowerPC EABI (embedded application binary interface). The PowerPC backend has been extended to generate the appropriate instructions for the reconfigurable hardware and data transfer, taking into account the information of the specific hardware implementations and system. Starting with an annotated C application, a complete design flow has been integrated to generate the executable bitstream for the reconfigurable processor. The flexible design of the proposed infrastructure allows to consider the special features of the reconfigurable architectures. In order to hide the reconfiguration latencies, we implemented an instruction-scheduling algorithm for the dynamic hardware configuration instructions. The algorithm schedules, in advance, the hardware configuration instructions, taking into account the conflicts for the reconfigurable hardware resources (FPGA area) between the hardware operations. To verify the Molen compiler, we used the multimedia video frame M-JPEG encoder of which the extended discrete cosine transform (DCT*) function was mapped on the FPGA. We obtained an overall speedup of 2.5 (about 84% efficiency over the maximal theoretical speedup of 2.96). The performance efficiency is achieved using automatically generated nonoptimized DCT* hardware implementation. The instruction-scheduling algorithm has been tested for DCT, quantization, and VLC operations. Based on simulation results, we determine that, while a simple scheduling produces a significant performance decrease, our proposed scheduling contributes for up to 16x M-JPEG encoder speedup.

The increase of the web traffic has created the need for web switches that are able to balance the traffic to the server farms based on their contents (e.g. layer 7 switching). In this paper we present a web switch implemented in a multi-processor reconfigurable platform augmented with hardware co-processors. The system supports the TCP splicing scheme to accelerate the routing of the packets by forwarding packets at the IP layer after a connection has been spliced. The processors are alleviated using special co-processors for the management of the spliced connection and the URL string parsing. The proposed scheme can sustain up to 927Mbps throughput for 64KB request file size consuming less than 1Watt in a Xilinx Virtex4 FPGA. Hence, the system provides an efficient combination of processor's flexibility and ASIC's performance. Finally, the system is compared against a network processor-based and a software content-based switch in terms of performance, area, and power.

As Intrusion Detection Systems (IDS)utilize more complex syntax to efficiently describe complex attacks, their processing requirements increase rapidly. Hardware and, even more, software platforms face difficulties in keeping up with the computationally intensive IDS tasks, and face overheads that can substantially diminish performance.In this paper we introduce a packet pre-filtering approach as a means to resolve, or at least alleviate, the increasing needs of current and future intrusion detection systems. We observe that it is very rare for a single incoming packet to fully or partially match more than a few tens of IDS rules. We capitalize on this observation selecting a small portion from each IDS rule to be matched in the pre-filtering step. The result of this partial match is a small subset of rules that are candidates for a full match. Given this pruned set of rules that can apply to a packet, a second-stage, full-match engine can sustain higher throughput.We use DefCon traces and recent Snort IDS rule-set,and show that matching the header and up to an 8-character prefix for each payload rule on each incoming packet can determine that on average 1.8 rules may apply on each packet, while the maximum number of rules to be checked across all packets is 32. Effectively, packet pre-filtering prevents matching at least 99%of the SNORT rules per packet and as a result minimizes processing and improves the scalability of the system. We also propose and evaluate the cost and performance of a reconfigurable architecture that uses multiple processing engines in order to exploit the benefits of pre-filtering.

In this paper, we propose a reconfigurable hardware accelerator for fixed-point-matrix-vector-multiply/add operations, capable to work on dense and sparse matrices formats. The prototyped hardware unit accommodates 4 dense or sparse matrix inputs and performs computations in a space parallel design achieving 4 multiplications and up to 12 additions at 120 MHz over an xc2vp100-6 FPGA device, reaching a throughput of 1.9 GOPS. A total of 11 units can be integrated in the same FPGA chip, achieving a performance of 21 GOPS.

Microprocessor vendors have provided special-purpose instructions such as psadbw and pdist to accelerate the sum-of-absolute differences (SAD) similarity measurement. The usefulness of these special-purpose instructions is limited except for the motion estimation kernel. This has several drawbacks. First, if the SAD becomes obsolete because a different similarity metric is going to be employed, then those special-purpose instructions are no longer useful. Second, these special instructions process 8-bit subwords only. This precision is not su cient for some kernels such as motion estimation in the transform domain. In addition, when employing other n-way parallel SIMD instructions to implement the SAD and sum-of-squared differences (SSD),the obtained speedup is much less than n. This is because there is a mismatch between the storage and the computational format. In this paper, we design and evaluate a variety of SIMD instructions for different data types. We synthesize special-purpose instructions using a few general-purpose SIMD instructions. In addition, we employ the extended subwords technique to avoid conversion overhead and to increase parallelism. In this technique there are four extra bits for every byte of register. The results show that using different SIMD instructions and extended subwords achieve a speedup ranging from 10.39 to 14.57 over C performance for SAD, SSD with interpolation, and SSD functions in the motion estimation kernel. While, MMX achieves a speedup ranging from 4.61 to 7.42. Additionally,the proposed SIMD instructions improve the performance of similarity measurement for image histograms by a factor ranging from 8.69 (1-way)to 11.70 (4-way) over C.While for MMX speedup is between 2.90 (1-way) and 4.33 (4-way).

In this paper, we propose two FPGA-area allocation algorithms based on profiling results for reducing the impact on performance of dynamic reconfiguration overheads. The problem of FPGA-area allocation is presented as a 0-1 integer linear programming problem and efficient solvers are incorporated for finding the optimal solutions. Additionally, we discuss the FPGA-area allocation problem in two scenarios. In the first scenario, all hardware operations are allocated on the FPGA while in the second scenario, any hardware operation can be switched to software execution in order to provide an overall performance improvement. We evaluate our proposed algorithms using the MPEG2 and MJPEG encoder multimedia benchmarks and the hardware implementations for SAD, DCT, IDCT, quantization and VLC tasks. We show that a significant performance improvement (up to 61 %for MPEG2 and 94 % for MJPEG) is to be achieved when the proposed algorithms are used, while the reconfiguration overhead is reduced by at least 36 % for MJPEG

The core goal of resource management is to establish a mutual agreement between a resource producer and a resource consumer by which the provider agrees to supply a capability that can be used to perform some tasks on behalf of the consumer. Market-based approaches introduce money and pricing as the technique for coordination between consumers and producers of resources. In this paper, we propose a market-based mechanism to allocate computational resources (CPU time) with a single central Market in a local Grid. In such a network whenever any node can offer idle CPU time to the Grid and whenever a node has some tasks waiting for free CPU, it may request the resource from the Grid. In our approach, consumers and producers are autonomous agents that make their own decisions according to their capabilities and their local knowledge. Continuous Double Auction model is used as a technique using which these selfish agents can coordinate their work and make their decision. The performance of this mechanism is evaluated and is compared with the simple FCFS mechanism.

In this paper, we propose a new internally buffered crossbar (IBC) switching architecture where the input and output distributed schedulers are embedded inside the crossbar fabric chip. As opposed to previous designs, where these schedulers are spread across input and output line cards, our design allows the schedulers to have cheap and fast access to the internal buffers, optimizes the flow control mechanism and makes the IBC more scalable. We employed the Xilinx Virtex-4FX platform to show the feasibility of our proposal and implemented a reconfigurable hardware based IBC switch with the maximum port count that we could fit on a single chip. The experiments suggest that a 24x24 IBC switch running a 10 Gbps port speed and a clock cycle time of 6.4 ns can be implemented.

In this paper the authors present the design and implementation of a dynamically reconfigurable system for packet queue scheduling. Two widely accepted queue schedulers have been implemented in reconfigurable logic in a way that can be interchanged based on the number of active queues and the quality of service (QoS) requirements. The first algorithm is the deficit weighted round robin (DWRR) that is used to support up to 2K queues. The second algorithm is the worst-case fair weighted fair queuing (WF2Q+) algorithm that is more accurate and closer to the ideal scheduling but the computation and memory requirements are higher. This scheme is used when the number of active queues is up to 341 queues or classes of services (CoS). The performance evaluation shows that these algorithms can be exchanged, thus obtaining higher accuracy, depending on the variant and the characteristics of the network traffic with negligible performance degradation due to the dynamic reconfiguration overhead

Recent intrusion detection systems (IDS) use regular expressions instead of static patterns as a more efficient way to represent hazardous packet payload contents. This paper focuses on regular expressions pattern matching engines implemented in reconfigurable hardware. A nondeterministic finite automata (NFA) based implementation was presented, which takes advantage of new basic building blocks to support more complex regular expressions than the previous approaches. The methodology is supported by a tool that automatically generates the circuitry for the given regular expressions, outputting VHDL representations ready for logic synthesis. Furthermore, techniques to reduce the area cost of our designs and maximize performance when targeting FPGAs were included. Experimental results show that our tool is able to generate a regular expression engine to match more than 500 IDS regular expressions (from the Snort ruleset) using only 25K logic cells and achieving 2 Gbps throughput on a Virtex2 and 2.9 on a Virtex4 device. Concerning the throughput per area required per matching non-meta character, our design is 3.4 and 10 times more efficient than previous ASIC and FPGA approaches, respectively

Using the existing reconfigurable network infrastructure of FPGAs, the reconfigurable FLUX interconnection networks was presented. That is, networks where the processing elements, forming a parallel system, have interconnects that are explicitly formed by request using reconfigurable fabric, rather than being fixed. Several experiments were performed to show the viability of our approach using the existing FPGA infrastructure (Virtex2Pro). The FLUX networks were compared against rigid/fixed networks using synthetic benchmarks. Experimental results show that reconfiguring the network to suit a given traffic pattern can be up to 2.6 and 5.5 times faster than a rigid mesh and binary tree network, respectively. In addition, the reconfiguration overhead can become negligible, given a traffic load that runs for sufficient time. This clearly shows that, based on the traffic pattern, different network configurations might be suitable. The implication of the above is that changing interconnects on demand could be beneficial

In this paper, we present a hardware solution to perform the commonly used memcpy operation with the goal to reduce the time to perform the actual memory copies. This is accomplished by taking advantage of the presence of a cache that is found next to many current-day (embedded) processors. Additionally, the currently presented solution assumes that to be copied data is already in the cache and is aligned by the cache-line size. We present the concept and implementation details of the proposed hardware module and the system used to experiment both our hardware and an optimized software implementation of the memcpy function. Experimental results show that the proposed hardware solution is at least 79% faster than an optimized hand-coded software solution

We consider the AES encryption/decryption algorithm and propose a memory based hardware design to support it. The proposed implementation is mapped on the Xilinx Virtex II Pro technology. Both the byte substitution and the polynomial multiplication of the AES algorithm are implemented in a single dual port on-chip memory block (BRAM). Two AES encryption/decryption cores have been designed and implemented on a prototyping XC2VP20-7 FPGA: a completely unrolled loop structure capable of achieving a throughput above 34 Gbits/s, with an implementation cost of 3513 slices and 80 BRAMs; and a fully folded structure, requiring only 515 slices and 12 BRAMs, capable of a throughput above 2 Gbits/s. To evaluate the proposed AES design, it has been embedded in a polymorphic processor organization, as a reconfigurable co-processor. Comparisons to state-of-the-art AES cores indicate that the proposed unfolded core outperforms the most recent works by 34% in throughput and requires 68% less reconfigurable area. Experimental results of both folded and unfolded AES cores suggest over 560% improvement in the throughput/slice metric when compared to the recent AES related art

In this paper an analysis of a dynamically reconfigurable processor is presented. The network processor incorporates a processor and a number of coprocessors that can be connected to the processor either directly or using a shared bus. The analysis investigates the configuration (in terms of co-processor distributions and interface), formulates the throughput that meets the network demands and the constraints of the platform (area, bus bandwidth, etc.) and takes into account the reconfiguration overhead. To find the configuration that meets the constraints, the platform is formulated into integer linear programming equations. Furthermore, the results of two case studies are presented, for a soft- and a hard-IP core processor, that uses three flows with different processing requirements (IP forward, encryption and media processing). In each case the number and the type of co-processors is shown in terms of the network distribution and the average packet size. Finally, the mapping of the framework in the Xilinx FPGA platform is discussed

Color space conversion is an important kernel in multimedia codecs such as JPEG and MPEG. When implemented using SIMD instructions, however, the performance improvement is often limited due to two reasons. First, corresponding color space components are stored at non-unit strides and, second, intermediate results can be larger than 8 bits. In this paper we show that extended subwords and the matrix register file (MRF) can be employed to mitigate these limitations. These techniques avoid rearrangement instructions and increase the number of subwords that are processed in parallel. Experimental results have been obtained by extending the SimpleScalar toolset. The results show that extended subwords and the MRF yield a speedup of up to 2.45x and 1.78x over MMX for the RGB-to-YCbCr and YCbCr-to-RGB kernels, respectively. Compared to C implementations, speedups of up to 10.09x and 6.74x, respectively, are obtained. Additionally, the results show that the speedup over MMX is higher for low issue rates. This means that extended subwords and the MRF are suitable techniques for embedded multimedia systems where high issue rates and out-of-order execution are too expensive. The results also show that using more registers improves performance substantially

We propose a scalable data alignment scheme incorporating module assignment functions and a generic addressing function for parallel access of randomly aligned rectangular blocks of data. The addressing function implicitly embeds the module assignment functions and it is separable, which potentially enables short critical paths and saves hardware resources. We also discuss the interface between the proposed memory organization and a linearly addressable memory. An implementation, suitable for MPEG-4 is presented and mapped onto an FPGA technology as a case study. Synthesis results indicate reasonably small hardware costs in the order of up to a few thousand FPGA slices for an exemplary 512/spl times/1024 two-dimensional (2-D) addressable space and a range of access pattern dimensions. Experiments suggest that speedups close to 8/spl times/ can be expected when compared to linear addressing schemes.

This paper focuses on SIMD implementations of the 2D discrete wavelet transform (DWT). The transforms considered are Daubechies' real-to-real method of four coefficients (Daub-4) and the integer-to-integer (5, 3) lifting scheme. Daub-4 is implemented using SSE and the lifting scheme using MMX, and their performance is compared to C implementations on a Pentium 4 processor. The MMX implementation of the lifting scheme is up to 4.0/spl times/ faster than the corresponding C program for a 1-level 2D DWT, while the SSE implementation of Daub-4 is up to 2.6/spl times/ faster than the C version. It is shown that for some image sizes, the performance is significantly hampered by the so called 64K aliasing problem, which occurs in the Pentium 4 when two data blocks are accessed that are a multiple of 64K apart. It is also shown that for the (5, 3) lifting scheme, a 12-bit word size is sufficient for a 5-level decomposition of the 2D DWT for images of up to 10 bits per pixel.

We introduce the midlfekicker metric for evaluating microarchitectures mostly during the design process. We assume a microarchitecture designed at a time T-1 and estimate if a new microarchitecture projected for time T has advantages over the microarchitecture designed at T-1 and remapped on the same technology at time T. We consider that microarchitects minimize the product cycles per instruction (CPI) x cycle time and estimate performance based on CPI with a soft-threshold to include cycle time product effects. Some measurements are also reported.

This paper presents some of the enhancements to the TriMedia instruction set architecture (ISA), as supported by the TM3270 media-processor. We show how the new operations are used to optimize the individual MPEG2 encoder kernels. Furthermore, we quantify the contribution of these kernels to overall MPEG2 encoder performance. We introduce two-slot operations, collapsed load operations with interpolations, and new multiplication operations. The encoder's texture pipeline for a bi-directionally predicted 8/spl times/8 block is performed in 358 VLIW instructions. MPEG2 encoding at CIF resolution at 25 frames per second is achieved within 33.5 MHz of processor performance.

Although the huge reconfiguration latency of the available FPGA platforms is a well-known shortcoming of the current FCCMs, little research in instruction scheduling has been undertaken to eliminate or diminish its negative influence on performance. In this paper, we introduce an instruction scheduling algorithm that minimizes the number of executed hardware reconfiguration instructions, taking into account the "FPGA area placement conflicts" between the available configurations. The algorithm is based on compiler analyses and feedback-directed techniques and it can switch from hardware execution to software execution for an operation, when the reconfiguration latency could not be reduced. The algorithm has been tested for the M-JPEG encoder application and the real hardware implementations for DCT quantization and VLC operations. Based on simulation results, we determine that, while a simple scheduling produces a significant performance decrease, our proposed scheduling contributes up to 16/spl times/ M-JPEG encoder speedup.

We introduce a 64-bit ANSI/IEEE Std 754-1985 floating point design of a hardware matrix multiplier optimized for FPGA implementations. A general block matrix multiplication algorithm, applicable for an arbitrary matrix size is proposed. The algorithm potentially enables optimum performance by exploiting the data locality and reusability incurred by the general matrix multiplication scheme and considering the limitations of the I/O bandwidth and the local storage volume. We implement a scalable linear array of processing elements (PE) supporting the proposed algorithm in the Xilinx Virtex II Pro technology. Synthesis results confirm a superior performance-area ratio compared to related recent works. Assuming the same FPGA chip, the same amount of local memory, and the same I/O bandwidth, our design outperforms related proposals by at least 1.7X and up to 18X consuming the least reconfigurable resources. A total of 39 PEs can be integrated into the xc2vp125-7 FPGA, reaching performance of, e.g., 15.6 GFLOPS with 1600 KB local memory and 400 MB/s external memory bandwidth.

In this paper, we consider scanning and analyzing packets in order to detect hazardous contents using pattern matching. We introduce a hardware perfect-hashing technique to access the memory that contains the matching patterns. A subsequent simple comparison between incoming data and memory output determines the match. We implement our scheme in reconfigurable hardware and show that we can achieve a throughput between 1.7 and 5.7 Gbps requiring only a few tens of FPGA memory blocks and 0.30 to 0.57 logic cells per matching character. We also show that our designs achieve at least 30% better efficiency compared to previous work, measured in throughput per area required per matching character.

This paper describes the (micro-) architecture of the TM3270 data cache. We present the cache parameters, such as cache size, associativity, line size and cache policies. We describe the data cache pipeline partitioning and the cache memory structure organization. We introduce "collapsed" and "two-slot" load operations. Furthermore, we introduce a combined software/hardware based technique for prefetching of data into the cache. We use an MPEG2 encoder application for a quantative evaluation of architectural aspects such as data prefetching and show that MPEG2 encoding at 352*288 resolution (CIF) at 25 frames per second can be performed in 33.3 MHz.

We present the TM3270 media-processor, the latest TriMedia VLIW processor, tuned to address the performance demands of standard definition video processing, combined with embedded processor requirements for the consumer market. We discuss the architecture, implementation, and its first realization in a 90 nm process technology. The processor incorporates instruction set architectural (ISA) extensions and a load/store unit optimized for the video-processing domain. The ISA extensions improve the performance on video processing kernels. The data cache policies and prefetching techniques allow for efficient access to multimedia data. Finally, power consumption and performance data are presented

This work investigates the single electron tunneling (SET) technology-based computation of basic addition related arithmetic functions, e.g., addition and multiplication, via a novel computation paradigm, which we refer to as electron counting arithmetic, that is based on controlling the transport of discrete quantities of electrons within the SET circuit. First, assuming that the number of controllable electrons within the system is unrestricted, we prove that the addition of two n-bit operands can be computed with a depth-2 network composed out of 3n+1 circuit elements and that the multiplication of two n-bit operands can be computed with a depth-3 network composed out of 4n-1 circuit elements. Second, assuming that the number of controllable electrons cannot be higher than a given constant r determined by practical limitations, we prove that the addition of two n-bit operands can be computed with a depth-(n/r+3) network composed out of 3n+1+n/r circuit elements. Under the same restriction, we suggest methods to reduce the addition network depth in the order of logn/r and to perform n-bit multiplication in an O(logn/r) delay. Finally, we propose SET-based implementations for a set of basic electron counting building blocks and implement a number of circuits operating under the electron counting paradigm as follows: 4-bit digital to analog converter, 5-bit analog to digital converter, 4-bit adder, and 3-bit multiplier. All proposed implementations are verified by means of simulation.

We consider two hardwired solutions for repetitive padding, a performance restricting algorithm for real time MPEG-4 execution. The first solution regards application specific implementations, the second regards general purpose processing. For the application specific implementations we propose a systolic array structure. To determine the chip area and speed, we have synthesized its VHDL models for two field-programmable gate array families-Xilinx and Altera. Depending on the implemented configuration, the unit can process between 77 K and 950 K macroblocks per second (MB/s) when mapped on FPGA chips containing less than 10 K logical gates and frequency capabilities below 100 MHz. The second approach regards an augmentation of a general-purpose arithmetic logical units with an extra functionality added to perform repetitive padding. At trivial hardware costs of a few hundred 2/spl times/2 AND-OR logic gates, we achieve an order of magnitude speed-up compared to nonaugmented general purpose processor padding. The proposed hardware solutions meet the requirements of all MPEG-4 visual profile levels. Both approaches have been proven to be scalable and fit into different architectural concepts and operand widths.

An instruction set extension designed to accelerate multimedia applications is presented and evaluated. In the proposed complex streamed instruction (CSI) set, a single instruction can process vector data streams of arbitrary length and stride and combines complex memory accesses (with implicit prefetching), program control for vector sectioning, and complex computations on multiple data in a single operation. In this way, CSI eliminates overhead instructions (such as instructions for data sectioning, alignment, reorganization, and packing/unpacking) often needed in applications utilizing MMX-like extensions and accelerates key multimedia kernels. Simulation results demonstrate that a superscalar processor extended with CSI outperforms the same processor enhanced with Sun's VIS extension by a factor of up to 7.77 on key multimedia kernels and by up to 35% on full applications.

An efficient low-cost, low-power hardware implementation of a novel run-time pixel coverage mask generation algorithm for embedded 3D graphics antialiasing purposes is presented. The proposed algorithm can be incorporated in any antialiasing scheme with prefiltering that is based on algebraic representation of primitive's edges. When compared with the state of the art, the described algorithm reduces several times the size of the required hardware implementation due to the utilization of the quadrant symmetry property allowing the storage of only the coverage mask information for a few representative edges in one of the quadrants of the plane, the rest of the information being derived on the fly via computationally inexpensive operations

This paper presents a versatile hardware/software co-simulation and co-design environment for embedded 3D graphics accelerators. The graphics accelerator design exploration framework (GRAAL) is an open system which offers a coherent development methodology based on an extensive library of systemC RTL models of graphics pipeline components. GRAAL incorporates tools to assist in the visual debugging of the graphics algorithms implemented in hardware, and to estimate the performance in terms of throughput, power consumption, and area.

Tile-based rendering (also called chunk rendering or bucket rendering) is a promising technique for low-power, 3D graphics platforms. This technique decomposes a scene into smaller regions called tiles and renders the tiles one-by-one. The advantage of this scheme is that a small memory integrated on the graphics accelerator can be used to store the color components and z values of one tile, so that accesses to the frame and z buffer are local, on-chip accesses which consume significantly less power than off-chip accesses. Tile-based rendering, however, requires that the primitives (commonly triangles) are sorted into bins corresponding to the tiles. This paper describes several algorithms for sorting the primitives into bins and evaluates their computational complexity and memory requirements. In addition, we present and evaluate several tests for determining if a triangle and a tile overlap. Experimental results obtained using several suitable 3D graphics workloads show that various trade-offs can be made and that, usually, better performance can be obtained by trading it for memory. This information allows the designer to select the appropriate method depending on the amount of memory available and the computational power.

In this paper, we present a full-static carry-skip adder designed to achieve low power dissipation and high-performance operation. To reduce the adder's delay and power consumption, the adder is divided into variable-sized blocks that balance the inputs to the carry chain. The optimum block sizes for minimizing the critical path delay with complementary carry generation are achieved. Within blocks, highly optimized carry look-ahead logic, which computes block generate and block propagate signals, is used to further decrease delay. The adder architecture decreases power consumption by reducing the number of logic levels, glitches, and transistors. To achieve balanced delay, input bits are grouped unevenly in the carry chain. This grouping reduces active power by minimizing extraneous glitches and transitions. The adder has been implemented in 130nm CMOS technology. At 1.2V and 25C, typical performance is 1.086GHz and power dissipation normalized to 600 MHz operation is 0.786 mW.

We present a prototype design of the MOLEN polymorphic processor, a CCM based on the co-processor architectural paradigm. The Xilinx Virtex II Pro technology is used as a prototyping platform. Experimental results prove the viability of the MOLEN concept. More precisely, the MPEG-2 application is accelerated very closely to its theoretical limits by implementing SAD, DCT and IDCT in reconfigurable hardware. The MPEG-2 encoder overall speedup is in the range between 2.80 and 2.96. The speedup of the MPEG-2 decoder varies between 1.56 and 1.63.

Summary form only given. A large number of scientific applications involve the operation on, and manipulation of sparse matrices. Irregular structure of these matrices, however, causes hardware that otherwise behaves efficient on regular data to severely suffer in performance when handling sparse matrices. In order to tackle this problem, a scheme consisting of a novel hierarchical sparse matrix (HiSM) storage format and an associated architectural concept have been presented. We propose, describe, and evaluate a hardware mechanism to facilitate transposition of a sparse matrix stored in the HiSM format. The proposed hardware is meant to be embedded in a vector processor as a functional unit. The main part of the unit consists of an s /spl times/ s word in-processor memory, where s is the vector processor's section size. We determine suitable parameters for the proposed mechanism and study the performance of HiSM-based transposition using the matrices from the D-SAB benchmark suite. We show that the HiSM-based transposition executed on a vector processor equipped with the proposed unit exhibits speedups of up to 32.0 times with respect to the transposition based on the most widely used compressed row storage format and executed on a standard vector processor. When considering average speedup, depending on the properties of matrices being transposed, such as the size and the organization of nonzero elements, a speedup by a factor between 15.5 and 20 has been observed.

In this paper we consider implementations of embedded 3D graphics and provide evidence indicating that 3D benchmarks employed for desktop computers are not suitable for mobile environments. Consequently, we present GraalBench, a set of 3D graphics workloads representative for contemporary and emerging mobile devices. In addition, we present detailed simulation results for a typical rasterization pipeline. The results show that the proposed benchmarks use only a part of the resources offered by current 3D graphics libraries. For instance, while each benchmark uses the texturing unit for more than 70% of the generated fragments, the alpha unit is employed for less than 13% of the fragments. The Fog unit was used for 84% of the fragments by one benchmark, but the other benchmarks did not use it at all. Our experiments on the proposed suite suggest that the texturing, depth and blending units should be implemented in hardware, while, for instance, the dithering unit may be omitted from a hardware implementation. Finally, we discuss the architectural implications of the obtained results for hardware implementations.

In this paper, we present a polymorphic processor paradigm incorporating both general-purpose and custom computing processing. The proposal incorporates an arbitrary number of programmable units, exposes the hardware to the programmers/designers, and allows them to modify and extend the processor functionality at will. To achieve the previously stated attributes, we present a new programming paradigm, a new instruction set architecture, a microcode-based microarchitecture, and a compiler methodology. The programming paradigm, in contrast with the conventional programming paradigms, allows general-purpose conventional code and hardware descriptions to coexist in a program: In our proposal, for a given instruction set architecture, a onetime instruction set extension of eight instructions, is sufficient to implement the reconfigurable functionality of the processor. We propose a microarchitecture based on reconfigurable hardware emulation to allow high-speed reconfiguration and execution. To prove the viability of the proposal, we experimented with the MPEG-2 encoder and decoder and a Xilinx Virtex II Pro FPGA. We have implemented three operations, SAD, DCT, and IDCT. The overall attainable application speedup for the MPEG-2 encoder and decoder is between 2.64-3.18 and between 1.56-1.94, respectively, representing between 93 percent and 98 percent of the theoretically obtainable speedups.

In this paper, a multiple-symbol parallel variable length decoding (VLD) scheme is introduced. The scheme is capable of decoding all the codewords in an N-bit block of encoded input data stream. The proposed method partially breaks the recursive dependency related to the VLD. First, all possible codewords in the block are detected in parallel and lengths are returned. The procedure results redundant number of codeword lengths from which incorrect values are removed by recursive selection. Next, the index for each symbol corresponding the detected codeword is generated from the length determining the page and the partial codeword defining the offset in symbol table. The symbol lookup can be performed independently from symbol table. Finally, the sum of the valid codeword lengths is provided to an external shifter aligning the encoded input stream for a new decoding cycle. In order to prove feasibility and determine the limiting factors of our proposal, the variable length decoder has been implemented on an field-programmable gate-array (FPGA) technology. When applied to MPEG-2 standard benchmark scenes, on average 4.8 codewords are decoded per cycle resulting in the throughput of 106 million symbols per second.

This paper presents a TriMedia processor extended with three reconfigurable designs for entropy decoding (ED), inverse quantization (IQ), and two-dimensional (2-D) inverse discrete cosine transform (IDCT), and assesses the performance gain that is provided by such extensions when performing MPEG2-compliant pel reconstruction. We first describe an extension of the TriMedia architecture, which consists of a multiple-context field programmable gate array (FPGA)-based reconfigurable functional unit (RFU), a configuration unit managing the reconfiguration of the RFU, and their associated instructions. Then, we address the computation of the ED, IQ, and 2-D IDCT tasks, and propose to provide reconfigurable hardware support for a variable-length decoder that can decode two symbols per call (VLD-2), an inverse quantizer that can dequantize four coefficients per call (IQ-4), and an 1-D IDCT (1-D IDCT). The most important aspects concerning the implementation of the FPGA-mapped VLD-2, IQ-4, and 1-D IDCT units, as well as the organization of the software routines calling these FPGA-mapped computing units are outlined. Experimental results indicate that by configuring each of the VLD-2, IQ-4, and 1-D IDCT units on a different FPGA context, and by activating the contexts as needed, the FPGA-augmented TriMedia can perform MPEG2-compliant pel reconstruction with an average speed-up of 1.4/spl times/ over the standard TriMedia.

We investigate the implementation of basic arithmetic functions, such as addition and multiplication, in single electron tunneling (SET) technology. First, we describe the SET equivalents of Boolean CMOS gates and threshold logic gates. Second, we propose a set of building blocks, which can be utilized for a novel design style, namely arithmetic operations performed by direct manipulation of the location of individual electrons within the system. Using this new set of building blocks, we propose several novel approaches for computing addition related arithmetic operations via the controlled transport of charge (individual electrons). In particular, we prove the following: n-bit addition can be implemented with a depth-2 network built with O(n) circuit elements; n-input parity can be computed with a depth-2 network constructed with O(n) circuit elements and the same applies for n/logn counters; multiple operand addition of m n-bit operands can be implemented with a depth-2 network using O(mn) circuit elements; and finally n-bit multiplication can be implemented with a depth-3 network built with O(n) circuit elements.

A case study on color space conversion (CSC) for MPEG decoding, carried out on the FPGA-augmented TriMedia processor is presented. That is, a transform from Y'CbCr color space to R'G'B' color space is addressed. First, we outline the extension of TriMedia architecture consisting of FPGA-based reconfigurable functional units (RFU) and associated instructions. Then we analyse a CSC (RFU-specific) instruction which can process four pixels per call, and propose a scheme to implement the CSC operation on RFU(s). When mapped on an ACEX EP1K100 FPGA, the proposed CSC exhibits a latency of 10 and a recovery of 2 TriMedia@200 MHz cycles, and occupies 57% of the device. By configuring the CSC facility on the RFU(s) at application load-time, color space conversion can be computed on FPGA-augmented TriMedia with 40% speed-up over the standard TriMedia.

The Complex Streamed Instruction (CSI) set is an ISA extension targeted at multimedia applications. CSI instructions process two-dimensional data streams stored in memory, performing sectioning, data alignment and conversion between different packed data types all in hardware. It has been shown previously that CSI provides significant speedups compared to current media ISA extensions such as MMX and VIS. This paper presents a detailed design of a unit that can execute CSI instructions under the assumption that the unit is interfaced with the L1 data cache. In particular it is shown that the complex, two-dimensional, address-generation calculations can be performed in a pipelined fashion and implemented using a three-stage pipeline with acceptable delay and hardware cost.

The paper presents a Design Space Exploration (DSE) experiment which has been carried out in order to determine the optimum FPGA-based Variable-Length Decoder (VLD) computing resource and its associated instructions, with respect to an entropy decoding task which is to be executed on the FPGA-augmented TriMedia/CPU64 processor We first outline the extension of the TriMedia/CPU64 architecture, which consists of an FPGA-based Reconfigurable Functional Unit (RFU) and the associated generic instructions. Then we address entropy decoding and propose a strategy to partially break the data dependency related to variable-length decoding. Three VLDs (VLD-1, VLD-2, VLD-3) instructions which can return 1, 2, or 3 symbols, respectively, are subsequently analyzed. After completing the DSE, we determined that VLD-2 instruction leads to the most efficient entropy decoding in terms of instruction cycles and FPGA area. The FPGA-based implementation of the computing resource associated to VLD-2 instruction is subsequently presented. When mapped on an ACEX EP1K100 FPGA from Altera, VLD-2 exhibits a latency of 8 TriMedia cycles, and uses all the Electronic Array Blocks and 51% of the logic cells of the device. The simulation results indicate that the VLD-2-based entropy decoder is 43% faster than its pure software counterpart.

This paper proposes a reconfigurable processing unit, which performs the MPEG-4 repetitive padding algorithm in real time. The padding unit has been implemented as a scalable systolic structure of processing elements. A generic array of PE has been described in VHDL, and the functionality of the unit has been validated by simulations. In order to determine the chip area and speed of the padding structure, we have synthesized the structure for two FPGA families - Xilinx and Altera. The simulation results indicate that the proposed padding unit can operate in a wide frequency range, depending on the implemented configuration. It is shown that it can process from tens up to hundreds of thousands MPEG-4 macroblocks per second. This allows the real-time requirements of all MPEG-4 profiles and levels to be met efficiently at trivial hardware costs. Finally, the trade-off between chip-area and operating speed is discussed and possible configuration alternatives are proposed.

In this paper a parallel Variable-Length Decoding (VLD) scheme is introduced. The scheme is capable of decoding all the codewords in an N-bit buffer whose accumulated codelength is at most N. The proposed method partially breaks the recursive dependency related to the MPEG-2 VLD. All possible codewords in the buffer are detected in parallel and the sum of the codelengths is provided to the external shifter aligning the variable-length coded input stream for a new decoding cycle. Two length detection mechanisms are proposed: the first approach determines the length in a parallel/serial fashion and the second using a new device denoted as MultiplexedAdd. In order to prove feasibility and determine the limiting factors of our proposal, the parallel/serial codeword detector with 32-bit input has been described in behavioral non-optimized VHDL and mapped onto Altera's ACEX EP1K100 FPGA. The implemented prototype exhibits a latency of 110 ns and uses 32% of the logic cells of the device. When applied to MPEG-2 standard benchmark scenes, on average 3.5 symbols are decoded per cycle.

This paper describes an experiment which aims to reveal the potential impact on performance yielded by augmenting a TriMedia-CPU64 processor with a multiple-context FPGA core. We first propose an extension of the TriMedia CPU64 architecture, which consists of a reconfigurable functional unit and its associated instructions. Then, we address the decoding of variable-length codes on such extended TriMedia and describe the architecture and FPGA-implementation of a variable-length decoder (VLD) computing facility. When mapped on an ACEX EP1K100 FPGA, the proposed VLD exhibits a latency of 7 cycles. Preliminary results indicate that by configuring each of the VLD and 1-D IDCT (which is described elsewhere) facilities on a different FPGA context, and by activating the contexts as needed, the augmented TriMedia can perform macroblock parsing followed up by pel reconstruction with an improvement of 20 - 25% over the standard TriMedia.

Assuming signed digit number representations, we investigate the implementation of some addition related operations assuming linear threshold networks. We measure the depth and size of the networks in terms of linear threshold gates. We show first that a depth-2 network with O(n) size, weight, and fan-in complexities can perform signed digit symmetric functions. Consequently, assuming radix-2 signed digit representation, we show that the two operand addition can be performed by a threshold network of depth-2 having O(n) size complexity and O(1) weight and fan-in complexities. Furthermore, we show that, assuming radix-(2n-1) signed digit representations, the multioperand addition can be computed by a depth-2 network with O(n/sup 3/) size with the weight and fan-in complexities being polynomially bounded. Finally, we show that multiplication can be performed by a linear threshold network of depth-3 with the size of O(n/sup 3/) requiring O(n/sup 3/) weights and O(n/sup 2/ log n) fan-in.

Piece-wise first- and second-order approximations are employed to design commonly used elementary function generators for neural-network emulators. Three novel schemes are proposed for the first-order approximations. The first scheme requires one multiplication, one addition, and a 28-byte lookup table. The second scheme requires one addition, a 14-byte lookup table, and no multiplication. The third scheme needs a 14-byte lookup table, no multiplication, and no addition. A second-order approximation approach provides better function precision; it requires more hardware and involves the computation of one multiplication and two additions and access to a 28-byte lookup table. We consider bit serial implementations of the schemes to reduce the hardware cost. The maximum delay for the four schemes ranges from 24- to 32-bit serial machine cycles; the second-order approximation approach has the largest delay. The proposed approach can be applied to compute other elementary function with proper considerations.

This paper investigates the possibility of using Java as a language for digital signal processing. We compare the performance of the fast Fourier transform using Java interpreters, compilers, and native execution. To characterize the Java language as a platform for signal processing, we have implemented a traditional FFT algorithm in both C and Java and compared their relative performances. Additionally, we have developed a Tensor algebra FFT library in both Matlab and Java. Each of the Tensor libraries has been coded to exploit the characteristics of the source language. Our results indicate that the latest Sun Solaris 2.6 Java platform can provide performance within 20% to 60% of optimized C code on short FFT computations. On longer FFT computations, Java is about a factor of 2 to 3 times less efficient than optimized C code. We expect this gap to narrow with better compiler technology and direct execution on Java processors such as the Delft-Java multithreaded processor. © 1998 John Wiley & Sons, Ltd.

In this paper a novel programmable approach to execute implicit routing algorithms is presented. The proposed router is based on an associative scheme that uses the attributes of the routing algorithm and the interconnection network topology. In this approach routing algorithms are mapped (or programmed) onto a set of bit-patterns that are matched in parallel. To show the applicability of this router, we have selected oblivious and fault-tolerant routing algorithms for ten different tree interconnection network topologies; however, the proposed scheme is flexible enough to accommodate other network topologies and routing algorithms. For the studied topologies, the number of required bit-patterns is of the same order as the topology degree. The proposed organization requires only one comparison and one read delays. This in turn yields a high-speed port assignment that is comparable to single topology routers (non-flexible routers). In the context of flexible router schemes, the proposed approach not only is one of the fastest but also requires a very small amount of hardware for its implementation.

This paper investigates threshold based neural networks for periodic symmetric Boolean functions and some related operations. It is shown that any n-input variable periodic symmetric Boolean function can be implemented with a feedforward linear threshold-based neural network with size of O(log n) and depth also of O(log n), both measured in terms of neurons. The maximum weight and fan-in values are in the order of O(n). Under the same assumptions on weight and fan-in values, an asymptotic bound of O(log n) for both size and depth of the network is also derived for symmetric Boolean functions that can be decomposed into a constant number of periodic symmetric Boolean subfunctions. Based on this results neural networks for serial binary addition and multiplication of n-bit operands are also proposed. It is shown that the serial addition can be computed with polynomially bounded weights and a maximum fan-in in the order of O(log n) in O(n= log n) serial cycles, where a serial cycle comprises a neural gate and a latch. The implementation cost is in the order of O(log n), in terms of neural gates, and in the order of O(log2 n), in terms of latches. Finally, it is shown that the serial multiplication can be computed in O(n) serial cycles with O(log n) size neural gate network, and with O(n log n) latches. The maximum weight value in the network is in the order of O(n2) and the maximum fan-in is in the order of O(n log n).

We address issues related to the definition of faults, errors and failures and their separability, and attribution to the different development processes of computing systems. In particular, we deal with historical databases, which presumably contain certain data (i.e., test failure data) and describe the methodology that can be used to analyze the database and obtain the pertinent information. The validation method may be of particular importance, especially when information from the database needs to be extrapolated for a purpose other than the one for which the database was developed. Our methodology was used to evaluate the historical data collected during the development of the IBM 4381 and 9370 family of computers, and to extrapolate the faults found during the function testing.

Two hardware methods for remedying the effects of true data dependences are studied. The first method dependence speculation, is used to eliminate address generation-load dependences. This is enabled by address prediction that permits load instructions to proceed speculatively without waiting for their address operands. The second technique, dependence collapsing, is used to eliminate data dependences by combining a dependence among multiple instructions into one instruction. The potential of these techniques for improving processor performance is demonstrated via trace-driven simulation. When both techniques are used with maximum issue widths of 4, 8, 16, and 32, the overall speedups in comparison to a base instruction level parallel machine are 1.20, 1.35, 1.51, and 1.66, respectively. In general, dependence collapsing contributes the majority of the improvement in performance. Under the dependence collapsing model, 298 to 478 of the total number of instructions in a trace may be collapsed. The distance separating the collapsed instructions is nearly always less than 8. Our experimentation also suggests that further performance improvements can be achieved by incorporating mechanisms that increase the address prediction rate.

In this paper, we report the findings of an investigation undertaken at IBM to determine whether or not existing software metrics are applicable to the microcode of large computer systems. As part of this investigation, we calculated several metrics from the microcode developed for the IBM 4381 and IBM 9370 computer systems, and used them as predictive parameters for a number of existing error prediction models. The microcode used in this case study exceeds 1.2 million lines of code written in 12 languages and comprises the microcode for the IBM ES/4381 and IBM ES/9370 computer systems. Our results suggest that only a few of the existing metrics are linearly independent, and that none of the metrics examined can be used in a regression model as a reliable error predictor.

In this paper we report on an empirical study conducted to determine whether existing software reliability models can be used to predict the errors incurred during the design, development and testing phases of the microcode of computer systems. A number of reliability models are reviewed and employed to predict the faults of the microcode development of the IBM 4381 and the IBM 9370 families of computer systems. Through the study of historical defect data from these two systems, we establish an empirical basis for the usefulness of such models in terms of accuracy in the prediction of the expected errors during the development of the microcode of computer systems.

In this paper we investigate the reduction of the size for small depth feed-forward linear threshold networks performing binary addition and related functions. For n bit operands we propose a depth-3 O(n2/log n) asymptotic size network for the binary addition with O polynomially bounded weights. We propose also a depth-3 addition of optimal O(n) asymptotic sits network and a depth-2 comparison of O(√n) asymptotic size network, both with O(2√n) asymptotic size of weight values. For existing architectural formats we show that our schemes, with equal or smaller depth networks, substantially outperform existing schemes in terms of size and fan-in requirements and on occasions in weight requirements.

A piecewise second order approximation scheme is proposed for computing the sigmoid function. The scheme provides high performance with low implementation cost; thus, it is suitable for hardwired cost effective neural emulators. It is shown that an implementation of the sigmoid generator outperforms, in both precision and speed, existing schemes using a bit serial pipelined implementation. The proposed generator requires one multiplication, no look-up table and no addition. It has been estimated that the sigmoid output is generated with a maximum computation delay of 21 bit serial machine cycles representing a speedup of 1.57 to 2.23 over other proposals.

A programmable associative approach to execute implicit routing algorithms is presented. Algorithms are mapped onto a set of bit-patterns that are matched in parallel. We have studied and mapped a large number of routing algorithms for a wide range of interconnection network topologies. Here we report three cases that illustrate the capabilities of the router scheme. For the studied topologies, the number of required bit-patterns is of the same order as the topology degree. The proposed approach is one of the fastest routers and requires a very small amount of hardware.

IBM Mwave/sup TM/ has developed a radically new approach for real-time video and graphics processing. A scalable array of processing elements (PEs) is configured as a "folded array" for effective execution of matrix and transpose operations. The single chip Mwave Folded Array Signal Transform processor (MFAST) is a scalable DSP that provides 10+ billion 16-bit operations-per-second@50 MHz, sustainable during algorithm execution. This paper describes key M.F.A.S.T. elements and a bounded 18-22 cycle 8/spl times/8-pixel 2-D discrete cosine transform (DCT) program, verified on VHDL and functional simulator models.

The paper describes a new approach to implement dynamically allocated multi-queue (DAMQ) switching elements using a technique called "self-compacting buffers". This technique is efficient in that the amount of hardware required to manage the buffers is relatively small; it offers high performance since it is an implementation of a DAMQ. The paper describes the self-compacting buffer architecture in detail, and compares it against a competing DAMQ switch design. It presents extensive simulation results comparing the performance of a self-compacting buffer switch against an ideal switch including several examples of k-ary n-cubes and delta networks. In addition, simulation results show how the performance of an entire network can be quickly and accurately approximated by simulating just a single switching element.>

The collection of data necessary to compute various software metrics constitutes a difficult task, especially for large projects written in multiple languages. We discus a number of issues associated with the collection of data for large commercial computer products and show that significant discrepancies in the value of some metrics may arise depending on the measurement method used. Using data collected from 4,635 microcode modules, which total s> 1.2 million lines of code and comprise the entire microcode of the IBM ES/4381 and IBM ES/9370 computer systems, we show the impact the computing methodology has on some studies associated with program metrics.

A high-performance 3-1 interlock collapsing ALU, i.e., an ALU that allows the execution of most execution interlocks in a single machine cycle, is presented. We focus on reducing the Boolean equations describing the device and the incorporation of new mechanisms in the interlock collapsing ALU design. In particular, we focus on the reduction of the critical path, regarding delay, for the interlock collapsing ALU implementation. It is shown that the delay associated with the implementation of the proposed device, in terms of logic stages, assuming a commonly available CMOS technology, is equivalent to the number of logic stages required for the implementation of a 3-1 binary adder. The resulting implementation demonstrates that the proposed 3-1 interlock collapsing ALU can be designed to outperform existing schemes for interlock collapsing ALU's by a factor of at least two. Finally, it is suggested that the proposed device can be used in the implementation of multiple instruction issuing machines, allowing the issuance and execution of interlocks in parallel and in a single machine cycle with no cycle time increases.>

Describes a question-answering system based on fuzzy logic. The proposed system provides the capability to assess whether a database contains information pertinent to a subject of interest by evaluating each comment in the database via a fuzzy evaluator that attributes a fuzzy membership value indicating its relationship to the subject. An assessment is provided for the database as a whole regarding its pertinence to the subject of interest, and consequently comments that are considered irrelevant to the subject may be discarded. The system has been developed for the examination of databases that were created during the development of the IBM 4381 computer systems, for bookkeeping purposes, to assess whether such databases contain information pertinent to the functional changes that occurred during the development cycle. The system, however, can be applied with minimal changes to a variety of circumstances, provided that the fundamental assumptions for the development of the membership functions are respected in the new application. Its applicability, without modifications, assuming the same subject of interest, is granted for databases comprising similar characteristics to that of the original database for which the system has been developed.>

Image processing for multimedia workstations is a computationally intensive task typically requiring special purpose hardware, for example a nearest neighbor mesh parallel machine organization. One type of nearest neighbor mesh computer consists of a K /spl times/ K square array of Processor Elements (PEs) where each PE is connected to the North, South, East, and West PEs only. In a torus configuration, there are a total of 2K/sup 2/ PE interfaces. Under the assumption of SIMD operation with unidirectional message and data transfers between the PEs, it is possible to reconfigure the array by placing the symmetric PEs together and share the north-south wires with the east-west wires, thereby reducing the wiring complexity in half, i.e. K/sup 2/ PE interfaces without affecting performance. This new machine organization is termed the Diagonal-Fold Mesh Array Processor, providing equivalent performance to a nearest neighbor mesh with half the wiring complexity for unidirectional data transferring algorithms.>

Presents a novel microparallel taxonomy for machines with multiple-instruction processing capabilities including VLIW, superscalar, and decoupled machines. The taxonomy is based upon the static or dynamic behavior of four abstract, operational stages that an instruction passes through. These stages are fetch, decode, execute, and retire. This two valued, four variable taxonomy results in sixteen ways that a processor's microarchitecture can be specified. The paper categorizes different machine instances that are either actual implementations or proposed systems within the taxonomy framework. Four new processor microarchitectures are postulated which provide additional features and are instances of the remaining unexplored microparallel classifications.>

A device capable of executing interlocked fixed point arithmetic logic unit (ALU) instructions in parallel with other instructions causing the execution interlock is presented. The device incorporates the design of a 3-1 ALU and can execute two's complement, unsigned binary, and binary logical operations. It is shown that status for ALU operations using a 3-1 ALU can be determined in a parallel fashion, resulting in the compliance of the proposed device with predetermined architectural behavior of single instruction execution. The device requires no more logic stages than does a 3-1 binary adder using a carry-save adder (CSA) followed by a carry-lookahead adder (CLA) design. Design considerations using a commonly available CMOS technology are also reported, indicating that the device will not increase the machine cycle of an implementation. It is suggested that the device can maintain full architectural compatibility.>

Three digital artificial neural network processors suitable for the emulation of fully interconnected neural networks are proposed. The processors use N(2) multipliers and an arrangement of tree structures that provide the communication and accumulation function either individually or in a combined manner using communicating adder trees. The performance for the emulation of an N-neuron network for all processors is achieved in 2log(2)N+C time units, where C is a constant equal to the multiplication, neuron activation, and internal fixed delays. The feasibility and characteristics of the proposed configurations to emulate single and/or multiple neural networks simultaneously are discussed, and a comparison with recently proposed neurocomputer architectures is reported.

A novel digital network architecture, the sequential pipelined neurocomputer (SPIN), is proposed. The SPIN processor emulates neural networks, producing high performance with minimal hardware by sequentially processing each neuron in the modeled completely connected network with a pipelined physical neuron structure. In addition to describing SPIN, performance equations are estimated for the ring systolic, the recurrent systolic array, and the neuromimetic neurocomputer architectures, three previously reported schemes for the emulation of neural networks, and a comparison with the SPIN architecture is reported.>

A multibit overlapped scanning multiplication algorithm for sign-magnitude and two's complement hard-wired multipliers is presented. The theorems necessary to construct the multiplication matrix for sign-magnitude representations are emphasized. Consequently, the algorithm for sign-magnitude multiplication and its variation to include two's complement numbers are presented. The proposed algorithm is compared to previous algorithms that generate a sign extended partial product matrix, with an implementation and with a study of the number of elements in the partial product matrix. The proposed algorithm is shown to yield significant savings over well known algorithms for the generation and the reduction of the partial product matrix of a multiplier designed with multibit overlapped scanning.>

Because of recent advances in technology, multibit scanning implementations can be considered that exceed three-bit and four-bit groupings. The generalized proof for the multibit overlapped scanning multiplication is introduced, and the multiplication process is discussed. The proofs are intended to establish the correctness of the decode and the actions taken to produce the multiplication of any valid scheme proposed in the past, and to dictate the correct decode and actions taken for any overlapped s-bit scanning algorithm such that s is a natural number greater than or equal to two. The multiplication is considered to be between two fractional numbers, which are represented in two's-complement form.>