Due to the emergence of new network applications, current IP lookup engines must support high bandwidth, low lookup latency, and the ongoing growth of IPv6 networks. However, the existing solutions are not designed to address jointly these three requirements. This paper introduces SHIP, an IPv6 lookup algorithm that exploits prefix characteristics to build a data structure designed to meet future application requirements. Based on the prefix length distribution and prefix density, prefixes are first clustered into groups sharing similar characteristics and then encoded in hybrid trie-trees. The resulting memory-efficient and scalable data structure can be stored in low-latency memories and allows the traversal process to be parallelized and pipelined in order to support high packet bandwidth in hardware. In addition, SHIP supports incremental updates. Evaluated on real and synthetic IPv6 prefix tables, SHIP has a logarithmic scaling factor in terms of the number of memory accesses and a linear memory consumption scaling. Compared with other well-known approaches, SHIP reduces the required amount of memory per prefix by 87%. When implemented on a state-of-the-art field-programmable gate array (FPGA), the proposed architecture can support processing 588 million packets per second.

The emergence of 5G networks and real-time applications across networks has a strong impact on the performance requirements of IP lookup engines. These engines must support not only high-bandwidth but also low-latency lookup operations. This paper presents the hardware architecture of a low-latency IPv6 lookup engine capable of supporting the bandwidth of current Ethernet links. The engine implements the SHIP lookup algorithm, which exploits prefix characteristics to build a compact and scalable data structure. The proposed hardware architecture leverages the characteristics of the data structure to support low-latency lookup operations, while making efficient use of memory. The architecture is described in C++, synthesized with a highlevel synthesis tool, then implemented on a Virtex-7 FPGA. Compared to the proposed IPv6 lookup architecture, other wellknown approaches use at least 87% more memory per prefix, while increasing the lookup latency by a factor of 2.3×.

Due to the rapid growth of traffic on the Internet, the IP lookup process imposes ever-growing performance requirements in order to avoid that it becomes a bottleneck during packet forwarding. This complex function is often implemented by hardware accelerators that are integrated with a processor. In this paper, we use a modified cache memory as an accelerator to perform IP lookup. Hashing is used for mapping each bucket of a hash table to a set of the cache memory. We show that, in the proposed scheme, a table of 26K prefixes fits into a cache of 1MB and the throughput achieved allows processing packets at wire speed over four 40Gb links.

Finding optimal/short-span Convolutional Self-Doubly Orthogonal (CDO) codes and Simplified-CDO (S-CDO) codes for a specified order J is computationally very challenging. This paper describes several optimizations that were applied to an implicitly-exhaustive search algorithm in order to reduce the time required for finding these types of codes. The resulting high-performance parallel implementation provides an impressive speedup that is greater than 16 300 (CDO,${\rm J} = 7$) and 6300 (S-CDO,${\rm J} = 8$) over the reference implicitly-exhaustive search algorithm, and greater than 2000$({\rm J} = 17)$over the fastest published CDO validation function used in high-performance pseudorandom search algorithms. These speedups are achieved through enhancements in the deterministic search-space reduction, and a vastly improved validation function that makes use of a novel data structure for enabling data-reuse and incremental computations. The resulting validation function speedup is greater than 60 000 (S-CDO,${\rm J} = 17$) and 190 000 (CDO,${\rm J} = 17$) when compared to its reference implementation. The combination of optimizations and load-balancing techniques allowed us to leverage hundreds of processor cores in order to complete an exhaustive search over a search space that is some$10^{14}$times larger than what was previously possible.

A novel parallel and implicitly-exhaustive search algorithm for finding, in systematic form, rate R=1/2 optimal-span Convolutional Self-Doubly Orthogonal (CDO) codes and Simplified Convolutional Self-Doubly Orthogonal (S-CDO) codes is presented. In order to obtain high-performance low-latency codecs with these codes, it is important to minimize their constraint length (or "span") for a given J number of generator connections. The proposed exhaustive algorithm uses algorithmic enhancements over the best previously published searching techniques, yielding new and improved codes: we were able to obtain new optimal-span CDO/S-CDO codes (having order J∈{9} and J∈{10,11} respectively), as well as new codes having the shortest spans published to date for higher values of J (J∈{10,12,...,17} and J∈{12,...,20} for CDO and S-CDO codes respectively). The new codes and their error performance are provided. An analysis of the evolution of the CDO/S-CDO code error performance as J increases is presented, and the shortest CDO/S-CDO code span values for each given J are compared.

Design space exploration is a delicate process whose success lays on the designers' shoulders. It is often based on a trial-and-error approach. Some basic metrics can be used to guide this process. In this paper, we explore accelerating loops from C-based specifications. We built a framework in which a design style, such as software-oriented or application-specific instruction-set processor (ASIP)-oriented design, can be specified. We also propose an exploration process that allows targeting the main aspects that limit acceleration and the actions that can be made to improve it. The process is based on new loop-oriented metrics that provide insight in key design issues. They help to determine which aspects of the design between data accesses and arithmetic logic unit (ALU)/control operations limit or allow leveraging loop acceleration opportunities. We profile some benchmarks from the signal and image processing fields, such as the Turbo Decoder and the JPEG algorithms, to illustrate how loop-oriented metrics help to point out aspects that limit or improve loop acceleration. The loop acceleration process was also used to explore design architectures that can leverage, as much as possible, the loop acceleration opportunities of the sum of absolute differences (SAD) algorithm.

Since ASIPs were introduced in the HW/SW architecture design space, application partitioning has become more complex. Designers have more ways to accelerate applications: with ASIPs of various kinds or with dedicated hardware modules. In this paper, we present loop-oriented metrics that will be used during design-space exploration for the partitioning process of C-based designs. These metrics help designers determine which aspect of loop iterations, between data memory accesses and ALU/Control operations, offers more acceleration potential. We implemented a profiler-scheduler LOOPPROF that gathers the metrics. Our tool also helps determine which optimization techniques such as data reuse are suitable for the considered code segments. We demonstrate the use of our tool by exploring the acceleration possibilities of the ELA Deinterlacer, a video processing algorithm.

Achievable performance gains, when accelerating applications using ASIPs, with a good sequence of specialized instructions, depends on the applications' available parallelism, and possibilities for optimizations and transformations. The type and number of operations, and the number of data transfers of the application are also critical factors. Much progress has been done on ASIP customized instruction-identification and selection research; they are usually based on operation clustering. In this paper, we propose to minimize the number of data transfers during execution of specialized instructions sequence by storing temporary values in user-defined registers. The method avoids costly data transfers and allows parallel processing of demanding computations. This method is applied to the design of an ASIP dedicated to edge line average deinterlacing, an algorithm used in HDTV. Experimental results show that our design method applied to this application, yields a speedup factor larger than 18.

The Zigangirov-Jelinek (stack) algorithm allows decoding convolutional codes with a small computational effort compared to the optimum Viterbi algorithm. However, it suffers from a variability of that computational effort that is highly undesirable. The paper describes an architecture that implements a multiple-path-like stack algorithm for reducing this variability. This architecture is organized as a linear structure comprising special processors for extending tree nodes, called extenders, and priority stacks for storing nodes in sorted metric order. The architecture is shown to have a good potential for reducing the computational variability without adding much overhead to the system. Simulations have shown that this architecture effectively reduces computational variability as the number of processors increases, even for a relatively large number of extenders. Simulations run for up to 16 extenders have also shown that using 4 to 16 extenders is a good choice. The architecture is also shown to reduce computational variability like the multiple path algorithm does, while having a better time performance.>