Traditionally, runtime management involving CPU sharing, real-time scheduling, etc., is provided by the runtime environment (typically an operating system) using hardware support such as timers and interrupts. However, due to stringent performance requirements on network processors, neither OS nor hardware mechanisms are typically feasible/available. Mapping packet processing tasks on network processors involves complex trade-offs to maximize parallelism and pipelining. Due to an increase in the size of the code store and complexity of application requirements, network processors are being programmed with heterogeneous threads that may execute code belonging to different tasks on a given micro-engine. Also, most network applications are streaming applications that are typically processed in a pipelined fashion. Thus, the tasks on different micro-engines are pipelined in such a way as to maximize the throughput. Tasks themselves could have different runtime performance demands. In this article, we focus on network processors on which hardware can only schedule threads in a round-robin fashion and no OS assistance is provided. We show that it is very difficult and inefficient for the programmer to meet the constraints of runtime management by coding them statically. Due to the infeasibility of hardware or OS solution (even in the near future), we undertake a compiler approach. We propose a complete compiler solution to automatically insert explicit context switch (ctx) instructions provided on the network processor such that the execution of threads is better manipulated at runtime to meet their constraints. Two approaches are presented that can control programs’ runtime behavior with different applicability and overheads. We show that it is feasible and also opens new application domains that would need heterogeneous thread programming. Such approaches would in general become important for multicore processors. Finally, our experiments show that the runtime constraints are enforced nearly ideally with minimal runtime degradation and small code growth.

Modern embedded processors with dedicated address generation unit support memory accesses through auto-increment/decrement addressing mode. The auto-increment/decrement mode, if properly utilized, can save address arithmetic instructions, reduce static and dynamic memory footprint of the program, and speed up the execution as well. Liao [1995, 1996] categorized this problem as Simple Offset Assignment (SOA) and General Offset Assignment (GOA), which involves storage layout of variables and assignment of address registers, respectively, proposing several heuristic solutions. This article proposes a new direction for investigating the solution space of the problem. The general idea [Zhuang 2003] is to perform simplification of the underlying access graph through coalescence of the memory locations of program variables. A comprehensive framework is proposed including coalescence-based offset assignment and post/pre-optimization. Variables not interfering with others (not simultaneously live at any program point) can be coalesced into the same memory location. Coalescing allows simplifications of the access graph yielding better SOA solutions; it also reduces the address register pressure to such low values that some GOA solutions become optimal. Moreover, it can reduce the memory footprint both statically and at runtime for stack variables. Our second optimization (post/pre-optimization) considers both post- and pre-modification mode for optimizing code across basic blocks, which makes it useful. Making use of both addressing modes further reduces SOA/GOA cost and our post/pre-optimization phase is optimal in selecting post or pre mode after variable offsets have been determined. We have shown the advantages of our framework over previous approaches to capture more opportunities to reduce both stack size and SOA/GOA cost, leading to more speedup.

It is well known that a large fraction of applications cannot be parallelized at compile time due to unpredictable data dependences such as indirect memory accesses and/or memory accesses guarded by data-dependent conditional statements. A significant body of prior work attempts to parallelize such applications using runtime data-dependence analysis and scheduling. Performance is highly dependent on the ratio of the dependence analysis overheads with respect to the actual amount of parallelism available in the code. We have found that the overheads are often high and the available parallelism is often low when evaluating applications on a modern multicore processor. We propose a novel software-based approach called dependence-aware scheduling to parallelize loops with unknown data dependences. Unlike prior work, our main goal is to reduce the negative impact of dependence computation, such that when there is not an opportunity of getting speedup, the code can still run without much slowdown. If there is an opportunity, dependence-aware scheduling is able to yield very impressive speedup. Our results indicate that dependence-aware scheduling can greatly improve performance, with up to 4x speedups, for a number of computation intensive applications. Furthermore, the results also show negligible slowdowns in a stress test, where parallelism is continuously detected but not exploited.

We present an approach for building calling context information useful for program understanding, performance analysis and optimizations. Our approach exploits a lightweight profiling mechanism providing partial call traces. The goal is to reconstruct calling context information as accurately as possible, and to help the user navigate through it. We propose three steps to merge partial call traces into a smaller number of partial calling context trees. We intend to minimize errors such that the final partial contexts represent actual components of the real calling context tree with a very high probability. The first step concatenates call traces based on their common sequences. The second step converts call traces into partial calling context trees, and the last step merges partial context trees through maximal matching. To gauge how well the merged trees represent the full calling context tree, several criteria are presented. Our results indicate that call traces are successfully merged into a small number of large calling context trees. The merged trees are highly accurate.We have also developed a semi-automatic tool to navigate across partial calling context trees for program understanding and performance analysis purposes. Our results for several Java benchmarks show that our merging strategies exhibit a maximum 1% inaccuracy when compared to the exact solution.

We present a study on data context for object-oriented programs. We first introduce several data structures related to data context that can properly organize object fields, object types and the access sequence in a compact manner. Our approach combines the collection of data context with commonly used garbage collectors in a virtual machine environment. The garbage collector maintains extra runtime data for the building of data contexts with minimal overhead. To save memory space and also the time spent on retrieving data, a shorter representation is proposed which sacrifices a small amount of accuracy. To further demonstrate the usefulness of data context for dynamic optimizations, we implemented a placement optimization that captures data accesses that frequently miss, and places relevant objects to reduce data cache misses and improve performance.

Although applications running on virtual machines, such as Java, can achieve platform independence, performance evaluation and analysis becomes difficult due to extra intermediate layers and the dynamic nature of virtual execution environment.

Because of stringent power constraints, aggressive latency-hiding approaches, such as prefetching, are absent in the state-of-the-art embedded processors. There are two main reasons that make prefetching power inefficient. First, compiler-inserted prefetch instructions increase code size and, therefore, could increase I-cache power. Second, inaccurate prefetching (especially for hardware prefetching) leads to high D-cache power consumption because of useless accesses. In this work, we show that it is possible to support power-efficient prefetching through bit-differential offset assignment. We target the prefetching of relocatable stack variables with a high degree of precision. By assigning the offsets of stack variables in such a way that most consecutive addresses differ by 1 bit, we can prefetch them with compact prefetch instructions to save I-cache power. The compiler first generates an access graph of consecutive memory references and then attempts a layout of the memory locations in the smallest hypercube. Each dimension of the hypercube represents a 1-bit differential addressing. The embedding is carried out in as compact a hypercube as possible in order to save memory space. Each load/store instruction carries a hint regarding prefetching the next memory reference by encoding its differential address with respect to the current one. To reduce D-cache power cost, we further attempt to assign offsets so that most of the consecutive accesses map to the same cache line. Our prefetching is done using a one entry line buffer [Wilson et al. 1996]. Consequently, many look-ups in D-cache reduce to incremental ones. This results in D-cache activity reduction and power savings. Our prefetcher requires both compiler and hardware support. In this paper, we provide implementation on the processor model close to ARM with small modification to the ISA. We tackle issues such as out-of-order commit, predication, and speculation through simple modifications to the processor pipeline on noncritical paths. Our goal in this work is to boost performance while maintaining/lowering power consumption. Our results show 12% speedup and slight power reduction. The runtime virtual space loss for stack and static data is about 11.8%.

Micro-architecture designers are very cautious about expanding the number of architected and exposed registers in the instruction set because increasing the register field adds to the code size, raises the I-cache and memory pressure, and may complicate the processor pipeline. Especially for low-end processors, encoding space could be extremely limited due to area and power considerations. On the other hand, the number of architected registers exposed to the compiler could directly affect the effectiveness of compiler analysis and optimization. For high-performance computers, register pressure can be higher than the available registers in some regions. This could be due to optimizations like aggressive function inlining, software pipelining, etc. The compiler cannot effectively perform compilation and optimization if only a small number of registers are exposed through the ISA. Therefore, it is crucial that more architected registers are available at the compiler's disposal, without expanding the code size significantly. In this article, we devise a new register encoding scheme, called differential encoding, that allows more registers to be addressed in the operand field of instructions than the direct encoding currently being used. We show that this can be implemented with very low overhead. Based upon differential encoding, we apply it in several ways such that the extra architected registers can benefit the performance. Three schemes are devised to integrate differential encoding with register allocation. We demonstrate that differential register allocation is helpful in improving the performance of both high-end and low-end processors. Moreover, we can combine it with software pipelining to provide more registers and reduce spills. Our results show that differential encoding significantly reduces the number of spills and speeds-up program execution. For a low-end configuration, we achieve over 14% speedup while keeping code size almost unaffected. For a high-end VLIW in-order machine, it can significantly speed-up loops with high register pressure (about 80% speedup) and the overall speedup is about 15%. Moreover, our scheme can be applied in an adaptive manner, making its overhead much smaller.

In this work, we present several compiler optimizations to reduce the overhead due to software protection. We first propose an aggressive rematerialization algorithm which attempts to maximally realize non-trusted values from other trusted values thereby avoiding the security cost for those non-trusted values. We further propose a compiler technique to utilize the secure storage in our machine model efficiently. To optimize the security cost on data that has to be stored in non-trusted storage, we propose a data grouping technique. Security operations can be performed over the group of data instead of over each piece separately. We show an interesting application of the data grouping technique to reduce the security cost. We test the effectiveness of our optimizations on a recently proposed software protection scheme that involves large overhead. Our results show that the above optimizations are effective and reduce the security overhead significantly.

Modern network processors support high levels of parallelism in packet processing by supporting multiple threads that execute on a micro-engine. Threads switch context upon encountering long latency memory accesses and this way the parallelism and memory access can be overlapped. Context switches in the typical network processor architectures such as the IXP are designed to be very fast. However, the low overhead is partly achieved by leaving register management to programs, with minimal support from the hardware. The complexity of the multi-engine, multi-threaded environment makes manual register management a daunting task, which is better left to a compiler. However, a purely static analysis is unable to achieve full utilization of the register file due to conservative estimates of liveness. A register that is live across a context switch point must be considered live for the duration of all other threads, and so it must be assumed to be unavailable to other threads. In addition, aliasing further reduces the effectiveness of static analysis. The net effect is a large number of idle cycles that are still present after static optimization. We propose a dynamic solution that requires minimal software and hardware support. On the software side, we take a pre-allocated binary file and annotate the potential context switch instructions with information about the dead registers. On the hardware side, we try to rename the transfer registers and addresses to dead general purpose registers and update the usage of registers. We then replace the long-latency memory instructions with fast move instructions in the architecture using the dynamic context. The results show up to 51% reduction in idle cycles and up to H% increase in the throughput for hand coded applications on Intel IXP 1200 network processor.

Mapping packet processing tasks on network processor micro-engines involves complex tradeoffs that relating to maximizing parallelism and pipelining. Due to an increase in the size of the code store and complexity of the application requirements, network processors are being programmed with heterogeneous threads that may execute code belonging to different tasks on a given micro-engine. Also, most network applications are streaming applications that are typically processed in a pipelined fashion. Thus, the tasks on different micro-engines are pipelined in such a way as to maximize the throughput. Tasks themselves could have different run time performance demands. Traditionally, runtime management involving processor sharing, real-time scheduling etc. is provided by the runtime environment (typically an operating system) using the hardware support for timers and interrupts that allows time slicing the resource amongst the tasks. However, due to stringent performance requirements on network processors (which process packets from very high speed network traffic), neither OS nor hardware mechanisms are typically feasible/available.In this paper, we show that it is very difficult and inefficient for the programmer to meet the constraints of runtime management by coding them statically. Due to the infeasibility of hardware or OS solution (even in the near future), the only choice left is a compiler approach.We propose a complete compiler solution to automatically insert explicit context switch (ctx) instructions provided on the processors so that the execution of programs is better manipulated at runtime to meet their constraints. We show that such an approach is feasible opening new application domains that would need heterogeneous thread programming. Such approaches would in general become important for multi-core processors.

In this paper, we propose a system called infeasible path detection system (IPDS) to combat memory tampering attacks causing invalid program control flows. In our system, the compiler analyzes correlations between branches and then the analyzed information is conveyed to the runtime system. The runtime system detects dynamic infeasible program paths by combining compiler determined information with runtime information to check the legality of the path taken during execution. IPDS achieves a zero false positive rate and can detect a high percentage of memory tampering for many attacks in which the tampering actually causes a change in control flow. Moreover, IPDS only incurs a modest amount of hardware resource and negligible performance penalty

Calling context profiles are used in many inter-procedural code optimizations and in overall program understanding. Unfortunately, the collection of profile information is highly intrusive due to the high frequency of method calls in most applications. Previously proposed calling-context profiling mechanisms consequently suffer from either low accuracy, high overhead, or both. We have developed a new approach for building the calling context tree at runtime, called adaptive bursting. By selectively inhibiting redundant profiling, this approach dramatically reduces overhead while preserving profile accuracy. We first demonstrate the drawbacks of previously proposed calling context profiling mechanisms. We show that a low-overhead solution using sampled stack-walking alone is less than 50% accurate, based on degree of overlap with a complete calling-context tree. We also show that a static bursting approach collects a highly accurate profile, but causes an unacceptable application slowdown. Our adaptive solution achieves 85% degree of overlap and provides an 88% hot-edge coverage when using a 0.1 hot-edge threshold, while dramatically reducing overhead compared to the static bursting approach.

Many modern embedded processors such as DSPs support partitioned memory banks (also called X--Y memory or dual-bank memory) along with parallel load/store instructions to achieve higher code density and performance. In order to effectively utilize the parallel load/store instructions, the compiler must partition the memory-resident values and assign them to X or Y bank. This paper gives a postregister allocation solution to merge the generated load/store instructions into their parallel counterparts. Simultaneously, our framework performs allocation of values to X or Y memory banks. We first remove as many load/stores and register--register moves as possible through an excellent iterated coalescing based register allocator by Appel and George [1996]. We then attempt to parallelize the generated load/stores using a multipass approach. The basic phase of our approach attempts the merger of load/stores without duplication and web splitting. We model this problem as a graph-coloring problem in which each value is colored as either X or Y. We then construct a motion scheduling graph (MSG), based on the range of motion for each load/store instruction. MSG reflects potential instructions that could be merged. We propose a notion of pseudofixed boundaries so that the load/store movement is less affected by register dependencies. We prove that the coloring problem for MSG is NP-complete and solve it with two different heuristic algorithms with different complexity. We then propose a two-level iterative process to attempt instruction duplication, variable duplication, web splitting, and local conflict elimination to effectively merge the remaining load/stores. Finally, we clean up some multiple-aliased load/stores. To improve the performance, we combine profiling information with each stage coupled with some modifications to the algorithm. We show that our framework results in parallelization of a large number of load/stores without much growth in data and code segments. The average speedup for our optimization pass reaches roughly 13% if no profile information is available and 17% with profile information. The average code and data segment growth is controlled within 13%.

Embedded systems are being deployed as a part of critical infrastructures and are vulnerable to malicious attacks due to internet accessibility. Intrusion detection systems have been proposed to protect computer systems from unauthorized penetration. Detecting an attack early on pays off since further damage is avoided and in some cases, resilient recovery could be adopted. This is especially important for embedded systems deployed in critical infrastructures such as Power Grids etc. where a timely intervention could save catastrophes. An intrusion detection system monitors dynamic program behavior against normal program behavior and raises an alert when an anomaly is detected. The normal behavior is learnt by the system through training and profiling.However, all current intrusion detection systems are purely software based and thus suffer from large performance degradation due to constant monitoring operations inserted in application code. Due to the potential performance overheads, software based solutions cannot monitor program behavior at a very fine level of granularity, thus leaving potential security holes as shown in the literature. Another important drawback of such methods is that they are unable to detect intrusions in near real time and the time lag could prove disastrous in real time embedded systems. In this paper, we propose a hardware-based approach to verify program execution paths of target applications dynamically and to detect anomalous executions. With hardware support, our approach offers multiple advantages over software based solutions including minor performance degradation, much stronger detection capability (a larger variety of attacks get detected) and zero-latency reaction upon an anomaly for near real time detection and thus much better security.

In this work, we develop a secret sharing based compiler solution to achieve confidentiality, integrity and availability (intrusion tolerance) of critical data together, rather than tackling them one by one as in previous approaches. Under our scheme, the compiler automatically identifies some critical data values, whereas the user specifies some others. The compiler generates code for scattering/assembling and verifying of those critical data values using secret sharing scheme. In this way, we achieve data confidentiality and integrity. We also provide mechanisms to gracefully recover upon data tampering, achieving intrusion tolerance. The implementation of our secret sharing scheme is carefully crafted to achieve low overhead. We further propose several compiler optimizations such as secret-sharing-aware register allocation, rematerialization etc. to reduce the cost of secret sharing further, making our scheme a practical solution in a high performance system.

A novel broadcast technique for wormhole-routed parallel computers based on recursion is presented in this paper. It works by partitioning the interconnection graph into a number of higher-level subgraphs. Then, we identify the transmission subgraph (TSG) in each subgraph. Both the higher-level subgraphs and the TSGs are recursively defined, i.e., we split each level i subgraph into several level i+1 subgraphs and identify-level i+1 TSGs accordingly. We first split and scatter the source message into the TSG of the original graph. Next, in each recursive round message transmissions are from lower-level TSGs to higher-level TSGs and all transmissions at the same level happen concurrently. The algorithm proceeds recursively from lower-level subgraphs to higher level subgraphs until each highest-level subgraph (a single node) gets the complete message. We have applied this general paradigm to a number of topologies including two or higher dimension mesh/torus and hypercube. Our results show considerable improvements over all other algorithms for a wide range of message sizes under both one-port and all-port models.

XOM-based secure processor has recently been introduced as a mechanism to provide copy and tamper resistant execution. XOM provides support for encryption/decryption and integrity checking. However, neither XOM nor any other current approach adequately addresses the problem of information leakage via the address bus. This paper shows that without address bus protection, the XOM model is severely crippled. Two realistic attacks are shown and experiments show that 70% of the code might be cracked and sensitive data might be exposed leading to serious security breaches.Although the problem of address bus leakage has been widely acknowledged both in industry and academia, no practical solution has ever been proposed that can provide an adequate security guarantee. The main reason is that the problem is very difficult to solve in practice due to severe performance degradation which accompanies most of the solutions. This paper presents an infrastructure called HIDE (Hardware-support for leakage-Immune Dynamic Execution) which provides a solution consisting of chunk-level protection with hardware support and a flexible interface which can be orchestrated through the proposed compiler optimization and user specifications that allow utilizing underlying hardware solution more efficiently to provide better security guarantees.Our results show that protecting both data and code with a high level of security guarantee is possible with negligible performance penalty (1.3% slowdown).

With more applications being deployed on embedded platforms, software protection becomes increasingly important. This problem is crucial on embedded systems like financial transaction terminals, pay-TV access-control decoders, where adversaries may easily gain full physical accesses to the systems and critical algorithms must be protected from being cracked. However, as this paper points out that protecting software with either encryption or obfuscation cannot completely preclude the control flow information from being leaked. Encryption has been widely studied and employed as a traditional approach for software protection, however, the control flow information is not 100% hidden with solely encrypting the code. On the other hand, pure software-based obfuscation has been proved inefficient to protect software due to its lack of theoretical foundation and considerable performance overhead introduced by complicated transformations. Moreover, even though obfuscation can prevent static reverse engineering, attacker can still successfully bypass the obfuscation by monitoring the dynamic program execution.To address all of these shortcomings, this paper presents a hardware assisted obfuscation technique that is capable of obfuscating the control flow information dynamically. Dynamic obfuscation changes memory access sequence on-the-fly and conceals recurrent instruction access sequences from being identified. Our scheme makes it provably difficult for the attacker to extract any useful information. Our results show that a high-level security protection is possible with only minor performance penalty. Finally, we show that our scheme can be implemented on embedded systems with very little hardware overhead.

Due to stringent power constraints, aggressive latency hiding approaches such as prefetching are absent in the state-of-the-art embedded processors. There are two main reasons that cause prefetching to be power inefficient. First, compiler inserted prefetch instructions increase code size, therefore could increase I-cache power. Secondly, inaccurate prefetching (esp. for hardware prefetching) leads to high D-cache power consumption due to the useless accesses. In this work, we show that it is possible to support power-efficient prefetching through bit-differentail offset assignment to stack variables.We target the prefetching of relocatable stack variables with a high degree of precision. By assigning the offsets of stack variables in such a way that most consecutive addresses differ by 1 bit, we can prefetch them with compact prefetch instructions to save I-cache power. The compiler first generates an access graph of consecutive memory references and then attempts a layout of the memory locations in the smallest hypercube. Each dimension of the hypercube represents a 1-bit differential addressing. The embedding is carried out in as compact a hypercube as possible in order to save memory space. Each load/store instruction carries a hint regarding prefetching the next memory reference by encoding its differential address with respect to the current one. To reduce D-cache power cost, we further attempt to assign offsets so that most of the consecutive accesses map to the same cache line. Our prefetching is done using a one entry line buffer[1]. As a consequence, many look-ups in D-cache reduce to incremental ones. This results in D-cache activity reduction and power savings.Our prefetching requires both compiler and hardware support. In this paper, we provide implementation on the ARM processor with small modification to the ARM ISA. We tackle issues about out of order commit, predication and speculation through simple modifications to the processor pipeline on non-critical paths. Our goal in this work is to boost performance while maintaining/lowering power consumption. Our results show 12% speed-up and slightly lower power consumption.

Most modern processors (either embedded or general purpose) contain higher number of physical registers than those exposed in the ISA. Due to a variety of reasons, this phenomenon is likely to continue especially on embedded systems where encoding space is very limited. Saving the encoding space leads to lower power consumption in the I-cache; on the other hand, harnessing more physical registers saves power in the memory subsystem and reduces latency as well. These design decisions however result in the difficulty of register allocation for a compiler due to limited number of exposed registers at ISA level. In this paper, we therefore propose a hardware managed register allocation scheme to allocate more physical registers at runtime and to utilize them. As a byproduct, we also show that hardware managed register allocation has other merits such as better exploitation of low register pressure regions, more flexible management of caller-save/callee-save registers, etc. Our approach consists of both compiler and hardware enhancements. On the compiler side we assign variables at various stack offsets such that the offsets indicate the relative allocation priorities at runtime. The hardware is modified to identify such spills and make decisions whether they should be put in the (invisible) physical registers based on their relative priorities. Finally, our results show slight improvement in the instructions per cycle counts (IPC) but significant power consumption reduction in the cache.

Modern network processors employ multi-threading to allow concurrency amongst multiple packet processing tasks. We studied the properties of applications running on the network processors and observed that their imbalanced register requirements across different threads at different program points could lead to poor performance. Many times application needs demand some threads to be more performance critical than others and thus by controlling the register allocation across threads one could impact the performance of the threads and get the desired performance properties for concurrent threads. This prompts our work.Our register allocator aims to distribute available registers to different threads according to their needs. The compiler analyzes the register needs of each thread both at the point of a context switch as well as internally. Compiler then designates some registers as shared and some as private to each thread. Shared registers are allocated across all threads explicitly by the compiler. Values that are live across a context switch can not be kept in shared registers due to safety reasons; thus, only those live ranges that are internal to the context switch can be safely allocated to shared registers. Spill can cause a context switch. and thus, the problems of context switch and allocation are closely coupled and we propose a solution to this problem. The proposed interference graphs (GIG,BIG,IIG) distinguish variables that must use a thread's private registers from those that can use shared registers. We first estimate the register requirement bounds, then reduce from the upper bound gradually to achieve a good register balance among threads. To reduce the register needs, move insertions are inserted at program points that split the live ranges or the nodes on the interference graph. We show that the lower bound is reachable via live range splitting and is adequate for our benchmark programs for simultaneously assigning them on different threads. As our objective, the number of move instructions is minimized.Empirical results show that the compiler is able to effectively control the register allocation across threads by maximizing the number of shared registers. Speed-up for performance critical threads ranges from 18 to 24% whereas degradation for performance of non-critical threads ranges only from 1 to 4%.

Mobile code carried by a mobile agent can automatically travel to several data sources in order to complete a designated program. Traditionally, most mobile agent systems [7][8][13] need explicit involvement of the programmer to designate migration and computation schedule of the agent. In this paper, we study the compiler-supported agent scheduling to optimize either the number of the migrations or the amount of data transfer. Two approaches are proposed and evaluated in our experiments, i.e. the static and dynamic scheduling algorithms. The first algorithm works totally offline. After converting the program control flow, graph (CFG) to program dependency graph (PDG), the schedule is worked out. On the other hand, in order to dynamically schedule the agent when it reaches predicate (control flow) nodes, our dynamic scheduling algorithm generates the motion schedule incrementally. Finally, our results show good improvement over unoptimized agent code both in terms of data transfer sizes and number of agent migrations.

Aggressive hardware-based and software-based prefetch algorithms for hiding memory access latencies were proposed to bridge the gap of the expanding speed disparity between processors and memory subsystems. As smaller L1 caches prevail in deep submicron processor designs in order to maintain short cache access cycles, cache pollution caused by ineffective prefetches is becoming a major challenge. When too aggressive prefetching are applied, ineffective prefetches not only can offset the benefits of benign prefetches due to pollution but also throttle bus bandwidth, leading to overall performance degradation. A hardware based cache pollution filtering mechanism is proposed to differentiate good and bad prefetches dynamically using a history table. Two schemes-peraddress (PA) based and program counter (PC) based-for triggering prefetches are proposed and evaluated. Our cache pollution filters work in tandem with both hardware and software prefetchers. As shown in the analysis of our simulated results, the cache pollution filters can significantly reduce the number of ineffective prefetches by over 90%, alleviating the excessive memory bandwidth induced by them. The IPC is improved by up to 9% as a result of reduced cache pollution and less competition for the limited number of cache ports

Modern embedded processors with dedicated address generation unit support memory access with indirect addressing mode with auto-increment and decrement. The auto-increment/decrement mode saves address arithmetic instructions.Liao et al [2][3] categorized this problem as simple offset assignment (SOA) problem and general offset assignment (GOA) problem, which involve storage layout of variables and assignment of address registers respectively proposing heuristic solutions. Later work [6][7] proposed improvements in the performance of Liao's solution by undertaking program and storage transformations that affect access sequence.The algorithms are incorporated into and evaluated on the commercial compiler provided by Motorola to boost code generation performance on the DSP 56k chip. Compared to previous approaches, variable coalescence with program reordering reduces SOA costs by 48% and GOA (2AR) costs by 66% for Mediabench and SPEC benchmarks. Moreover, we show that our approach obtains theoretically optimal solution (zero cost) for the GOA problem in 87% of the cases with just 2 address registers and in 94% of the cases with 3 address registers.