Application-specific instruction-set processors (ASIPs) utilize customized instructions to speedup a specific application or a set of applications. Thus, ASIPs execute the application(s) faster and are energy efficient compared to general-purpose processors. State-of-the-art custom instruction design methods typically target small applications or kernels of an application, often demanding an instruction designer's ingenuity at some point (semi-automated) to achieve design goals. In this article, for the first time, a fully automated system called FINDER is presented, which finds parallel instructions for ASIPs to improve the performance of large applications and generate FLIX (flexible instructions extension instructions, which are VLIW-type instructions) configurations. Note that we do not synthesize accelerators to speedup. We demonstrate that the proposed method scales well when applied to large applications. The proposed method described in this article models parallel instructions as a graph, analyzes the graph, and finds maximum weighted cliques to create FLIX configurations for a given application. Moreover, hardware reuse within multiple FLIX configurations is incorporated into the methodology. From the configurations, a commercial processor design tool (Xtensa) creates the FLIX instructions and integrates it into a base processor. The results show that the FINDER methodology generates FLIX configurations which shows speedups of up to 2.1× for large applications and 2.7× for smaller applications when compared to the base processor (without FLIX instructions). The logic area increase on average is 11%, and in the worst case is 22%. The energy-delay product can be up to 7.3× lower than when the application is executed on the base processor. Compared to the state-of-the-art systems which are typically demonstrated on applications with less than 100 lines of code, FINDER is capable of analyzing applications with thousands of lines of code and can automatically generate instructions for such applications.

CPU caches have become an essential component in many computer systems as they can significantly increase system performance by alleviating the effects of memory latency. For many designers part of the system design flow is the selection of an appropriately configured cache, a task which can be performed using cache simulators. Exploring the entire design space through precise cache simulation is a lengthy process, and while certain cache replacement policies have been optimised for fast simulation execution (such as LRU and FIFO), no effective optimisations have been proposed for an extremely effective replacement policy: Pseudo Least Recently Used tree-based, also known as PLRUt. In this paper we are the first to present a number of characteristics of the PLRUt replacement policy that lend themselves to the design of an optimised hash table-based cache simulator. We demonstrate that our optimised simulator is up to 1.93x faster than an un-optimised implementation.

Pipeline of processors allow the execution of a sequential streaming program on multiple processors. However, partitioning sequential code for Multiprocessor Systems-on-Chips (MPSoCs), and then creating the MPSoC platform for the sequential code to execute, is a challenging problem. Parallelizing/pipelining statements within a control loop will improve the throughput of each iteration and the overall performance. Existing techniques, such as OpenMP, for parallelizing control loops is agnostic of the underlying MPSoC architecture, thus limiting the possibilities for further parallelisation. Previous techniques related to distribution of statements to MPSoCs considered homo geneous processors and not automated. In this paper, we propose a novel automated parallelization/ pipelining approach to synthesize a heterogeneous distributed pipelined MPSoC to improve the throughput of a loop (critical for streaming applications). An Integer Linear Programming (ILP)-based formulation to map statements to processor configurations is presented, in order to find the most suitable heterogeneous processor configurations for maximal throughput. Our approach complements state-of-the-art parallelization techniques, such as OpenMP, to further improve the performance of an application. A complete MPSoC platform, for the Tensilica framework, is automatically generated within minutes using our approach for the tested applications.

A pipeline of processors can increase the throughput of streaming applications significantly. Communication between processors in such a system can occur via FIFOs, shared memory or both. The use of a cache for the shared memory can improve performance. To see the effect of differing cache configurations (size, line size and associativity) on performance, typical full system simulations for each differing cache configuration must be performed. Rapid estimation of performance is difficult due to the cache being accessed by many processors. In this paper, for the first time, we show a method to estimate the performance of a pipelined processor system in the presence of differing sizes of caches which connect to the main memory. By performing just a few full simulations for a few cache configurations, and by using these simulations to estimate the hits and misses for other configurations, and then by carefully annotating the times of traces by the estimated hits and misses, we are able to estimate the throughput of a pipelined system to within 90% of its actual value. The estimation time takes less than 10% of full simulation time. The estimated values have a fidelity of 0.97 on average (1 being perfectly correlated) with the actual values.

The Multiprocessor System-on-Chip (MPSoC) paradigm as a viable implementation platform for parallel processing has expanded to encompass embedded devices. The ability to execute code in parallel gives MPSoCs the potential to achieve high performance with low power consumption. In order for sequential legacy code to take advantage of the MPSoC design paradigm, it must first be partitioned into data flow graphs (such as Kahn Process Networks — KPNs) to ensure the data elements can be correctly passed between the separate processing elements that operate on them. Existing techniques are inadequate for use in complex legacy code. This paper proposes SDG2KPN, a System Dependency Graph to KPN conversion methodology targeting the conversion of legacy code. By creating KPNs at the granularity of the function-/procedure-level, SDG2KPN is the first of its kind to support shared and global variables as well as many more program patterns/application types. We also provide a design flow which allows the creation of MPSoC systems utilizing the produced KPNs. We demonstrate the applicability of our approach by retargeting several sequential applications to the Tensilica MPSoC framework. Our system parallelized AES, an application of 950 lines, in 4.8 seconds, while H.264, of 57896 lines, took 164.9 seconds to parallelize.

Judicious selection of cache configuration is critical in embedded systems as the cache design can impact power consumption and processor throughput. A large cache increases cache hits but requires more hardware and more power, and will be slower for each access. A smaller cache is more economical and faster per access, but may result in significantly more cache misses resulting in a slower system. For a given application or a class of applications on a given hardware system, the designer can aim to optimise cache configuration through cache simulation. We present here the first multiple cache simulator based on hardware. The FPGA implementation is characterised by a trace consumption rate of 100MHz making our cache simulation core up to 53x faster, for a set of benchmarks, than the fastest software based cache simulator. Our cache simulator can determine the hit rates of 308 cache configurations, of which it can determine the hit rates of 44 simultaneously.

Cache memories have become an essential component in modern processors. To find the cache configuration that best fits the targeted power, timing and cost criteria of the system, designers conventionally run a lengthy cache simulation in software. In this paper we present MASH{fifo}, the first Multiple cAche Simulator in Hardware (MASH) supporting the FIFO replacement policy. We measured a speedup of up to 11x when compared to the fastest software alternative, CIPARSim. We also investigate an in-system implementation where multiple cache simulation is performed in real time from within an embedded system.

Embedded systems are ubiquitous and are deployed in a large range of applications. Designing and fabricating Integrated Circuits (ICs) targeting such different range of applications is expensive. Designers seek flexible processors which efficiently execute a multitude of applications. FPGAs are considered affordable, but design cost, high reconfiguration delay and power consumption are all prohibitive. In this paper, we propose a novel ASIC based flexible MPSoC architecture, which can execute separate tasks in parallel, and it can be configured to execute single task with wide data widths or execute multiple tasks with varying data widths. The architecture presented, called Dynamically Reconfigurable MPSoC Architecture (DRMA), can be rapidly reconfigured through instructions. We present applications as case studies to showcase the flexibility and efficacy of DRMA. Results show for an additional area overhead of about 5%, the system is capable of working as four 32-bit processors, a single 128 bit processor or as a pipelined processing system.

An application's cache miss rate is used in timing analysis, system performance prediction and in deciding the best cache memory for an embedded system to meet tighter constraints. Single-pass simulation allows a designer to find the number of cache misses quickly and accurately on various cache memories. Such single-pass simulation systems have previously relied heavily on cache inclusion properties, which allowed rapid simulation of cache configurations for different applications. Thus far the only inclusion properties discovered were applicable to the Least Recently Used (LRU) replacement policy based caches. However, LRU based caches are rarely implemented in real life due to their circuit complexity at larger cache associativities. Embedded processors typically use a FIFO replacement policy in their caches instead, for which there are no full inclusion properties to exploit. In this paper, for the first time, we introduce a cache property called the “Intersection Property” that helps to reduce single-pass simulation time in a manner similar to inclusion property. An intersection property defines conditions that if met, prove a particular element exists in larger caches, thus avoiding further search time. We have discussed three such intersection properties for caches using the FIFO replacement policy in this paper. A rapid single-pass FIFO cache simulator “CIPARSim” has also been proposed. CIPARSim is the first single-pass simulator dependent on the FIFO cache properties to reduce simulation time significantly. CIPARSim's simulation time was up to 5 times faster (on average 3 times faster) compared to the state of the art single-pass FIFO cache simulator for the cache configurations tested. CIPARSim produces the cache hit and miss rates of an application accurately on various cache configurations. During simulation, CIPARSim's intersection properties alone predict up to 90% (on average 65%) of the total hits, reducing simulation time immensely.

Embedded systems designers are free to choose the most suitable configuration of L1 cache in modern processor based SoCs. Choosing the appropriate L1 cache configuration necessitates the simulation of long memory access traces to accurately obtain hit/miss rates. The long execution time taken to simulate these traces, particularly separate simulation for each configuration is a major drawback. Researchers have proposed techniques to speed up the simulation of caches with LRU replacement policy. These techniques are of little use in the majority of embedded processors as these processors utilize Round-robin policy based caches. In this paper we propose a fast L1 cache simulation approach, called SCUD (Sorted Collection of Unique Data), for caches with the Round-robin policy. SCUD is a single-pass cache simulator that can simulate multiple L1 cache configurations (with varying set sizes and associativities) by reading the application trace once. Utilizing fast binary searches in a novel data structure, SCUD simulates an application trace significantly faster than a widely used single configuration cache simulator (Dinero IV). We show SCUD can simulate a set of cache configurations up to 57 times faster than Dinero IV. SCUD shows an average speed up of 19.34 times over Dinero IV for Mediabench applications, and an average speed up of over 10 times for SPEC CPU2000 applications.

Increasing the speed of cache simulation to obtain hit/miss rates enables performance estimation, cache exploration for embedded systems and energy estimation. Previously, such simulations, particularly exact approaches, have been exclusively for caches which utilize the least recently used (LRU) replacement policy. In this paper, we propose a new, fast and exact cache simulation method for the First In First Out(FIFO) replacement policy. This method, called DEW, is able to simulate multiple level 1 cache configurations (different set sizes, associativities, and block sizes) with FIFO replacement policy. DEW utilizes a binomial tree based representation of cache configurations and a novel searching method to speed up simulation over single cache simulators like Dinero IV. Depending on different cache block sizes and benchmark applications, DEW operates around 8 to 40 times faster than Dinero IV. Dinero IV compares 2.17 to 19.42 times more cache ways than DEW to determine accurate miss rates.

We consider the problem of on-chip L2 cache management and replacement policies. We propose a new adaptive cache replacement policy, called Dueling CLOCK (DC), that has several advantages over the Least Recently Used (LRU) cache replacement policy.

Packet classification is an important aspect of modern network systems. Packet classification systems have traditionally been built utilizing Ternary Content Addressable Memory (TCAM) due to the high throughput needed. However, TCAMs are expensive in terms of area and power consumption. An alternative to TCAM based systems using SRAM and a novel rule encoding method has been proposed to match multiple packets simultaneously (using multiple store_compare_units). This alternative achieves similar or better throughput than the traditional TCAM approach while occupying smaller space and consuming less energy. This paper revamps the existing SRAM-based architecture to reduce area and power consumption without threatening throughput. Two methods are shown. The first method allows for range encoding SRAMs to be shared between store_compare_units (SCUs) to lower area and power consumption with minor effect on throughput. The second method discusses a hybrid system allowing rules with prefixes (single rules) and ranges (rules which match a range of addresses, usually translated to many prefixes) to exist in parallel for the same domain. This allows for lower power consumption than utilizing fixed range encoding due to optimization of the ruleset. Results show that this hybrid architecture saves more than 20% of power/field if half of the TCP ports contain ranges (and the other half contains prefixes). The new extensions have been tested in over ten benchmarks (including the SNORT ruleset) to verify the claimed improvements.

State-of-the-art hardware based techniques achieve high performance and maximize efficiency of packet classification applications. The predominant example of these, ternary content addressable memory (TCAM) based packet classification systems can achieve much higher throughput than software-based techniques. However, they suffer from high power consumption due to the highly parallel architecture and lack high-throughput range encoding techniques. In this paper, we propose a novel SRAM-based packet classification architecture with packet-side search key range encoding units, significantly reducing energy consumption without reducing the throughput from that of TCAM and additionally allowing range matching at wire speed. LOP_RE is a flexible packet classification system which can be customized to the requirement of the application. Ten different benchmarks were tested, with results showing that LOP_RE architectures provide high lookup rates and throughput, and consume low power and energy. Compared with a TCAM-based packet classification system (without range encoding) implemented in 65nm CMOS technology, LOP_RE can save 65% energy consumption for the same rule set over these benchmarks.

Numerous dynamic power management techniques have been proposed which utilize the knowledge of processor power/energy consumption at run-time. So far, no efficient method to provide run-time power/energy data has been presented. Current measurement systems draw too much power to be used in small embedded designs and existing performance counters can not provide sufficient information for run-time optimization. This paper presents a novel methodology to solve the problem of run-time power optimization by designing a processor that estimates its own power/energy consumption. Estimation is performed by the addition of small counters that tally events which consume power. This methodology has been applied to an existing processor resulting in an average power error of 2% and energy estimation error of 1.5%. The system adds little impact to the design, with only a 4.9% increase in chip area and a 3% increase in average power consumption. A case study of an application that utilizes the processor showcases the benefits the methodology enables in dynamic power optimization.