With the emergence of software delivery platforms, code compression has become an important system component that strongly affects performance. This article presents PPMexe, a compression mechanism for program binaries that analyzes their syntax and semantics to achieve superior compression ratios. We use the generic paradigm of prediction by partial matching (PPM) as the foundation of our compression codec. PPMexe combines PPM with two preprocessing steps: ( i ) instruction rescheduling to improve prediction rates and ( ii ) heuristic partitioning of a program binary into streams with high autocorrelation. We improve the traditional PPM algorithm by ( iii ) using an additional alphabet of frequent variable-length supersymbols extracted from the input stream of fixed-length symbols. In addition, PPMexe features ( iv ) a low-overhead mechanism that enables decompression starting from an arbitrary instruction of the executable, a property pivotal for runtime software delivery. We implemented PPMexe for x86 binaries and tested it on several large applications. Binaries compressed using PPMexe were 18--24% smaller than files created using off-the-shelf PPMD, one of the best available compressors

Deep submicrometer technology scaling has two major ramifications on the design process. First, reduced feature size significantly increases wire delay, thus resulting in critical paths being dominated by global interconnect rather than gate delays. Second, an ultrahigh level of integration mandates design of systems-on-chip that encompass numerous design blocks of decreased functional granularity and increased communication demands. The convergence of these two factors emphasizes the importance of the on-chip bus network as one of the crucial high-performance enablers for future systems-on-chip. An on-chip bus-network design methodology and corresponding set of tools which, for the first time, close the synthesis loop between system and physical design have been developed. The approach has three components: a communication profiler, a bus-network designer, and a fast approximate floorplanner. The communication profiler collects run-time information about the traffic between system cores. The bus-network design component optimizes the bus-network structure by coordinating information from the other two components. The floorplanner aims at creating a feasible floorplan; it also sends feedback about the most constrained parts of the network. The effectiveness of our bus-network design approach on a number of multicore designs is demonstrated

Rapid prototyping and development of in-circuit and FPGA-based emulators as key accelerators for fast time-to-market has resulted in a need for efficient error correction mechanisms. Fabricated or emulated prototypes upon error diagnosis require an effective engineering change (EC). We introduce a novel design methodology which consists of pre- and post-processing techniques that enable EC with minimal perturbation. Initially, in a synthesis preprocessing step, the original design specification is augmented with additional design constraints which ensure flexibility for future correction. Upon alteration of the initial design, a new post-processing technique achieves the desired functionality with near-minimal perturbation of the initially optimized design. The key contribution is a constraint manipulation technique which enables the reduction of an arbitrary EC problem into its corresponding classical synthesis problem. As a result, in both pre- and post-processing for EC, classical synthesis algorithms can be used to enable flexibility and perform the correction process. We demonstrate the developed EC methodology on a set of behavioral and system synthesis tasks.

Preventing execution of unauthorized software on a given computer plays a pivotal role in system security. The key problem is that although a program at the beginning of its execution can be verified as authentic, its execution flow can be redirected to externally injected malicious code using, for example, a buffer overflow exploit. We introduce a novel, simplified, hardware-assisted intrusion prevention platform. Our platform introduces overlapping of program execution and MAC verification. It partitions a program binary into blocks of instructions. Each block is signed using a keyed MAC that is attached as a footer to the block. When the control flow reaches a particular block, its instructions are speculatively executed, while dedicated hardware verifies the attached MAC at run-time. The computation state is preserved during speculative execution using a mediating buffer placed between the processor and L1 data cache. Upon MAC verification, the results from this buffer are propagated externally. Central to this paper is the proposal of a novel optimization technique that initially identifies instructions that are likely to stall execution, and reorders basic blocks within a given instruction block to minimize the execution overhead. While the presented optimization technique is problem specific, it is flexible such that it can be adjusted for different optimization goals. Preliminary results showed that our optimization methods produced an average overhead reduction of 60% on the SPEC2000 benchmark suite and Microsoft Visual FoxPro.

With the emergence of software delivery platforms such as Microsoft's .NET, the reduced size of transmitted binaries has become a very important system parameter, strongly affecting system performance. We present two novel pre-processing steps for code compression that explore program binaries' syntax and semantics to achieve superior compression ratios. The first preprocessing step involves heuristic partitioning of a program binary into streams with high auto-correlation. The second preprocessing step uses code optimization via instruction rescheduling in order to improve prediction probabilities for a given compression engine. We have developed three heuristics for instruction rescheduling that explore tradeoffs of the solution quality versus algorithm run-time. The pre-processing steps are integrated with the generic paradigm of prediction by partial matching (PPM) which is the basis of our compression codec. The compression algorithm is implemented for x86 binaries and tested on several large Microsoft applications. Binaries compressed using our compression codec are 18-24% smaller than those compressed using the best available off-the-shelf compressor.

The prediction by partial matching (PPM) algorithm uses a cumulative frequency count of input symbols in different contexts to estimate its probability distribution. Compression ratios yielded by the PPM algorithm have not instigated broader use of this scheme mainly because of its high demand for computational resources. An algorithm that improves the memory usage by the PPM model is presented. The algorithm identifies and removes portions of the PPM model, which are not contributing toward better modeling of the input data. As a result, our algorithm improves the average compression ratio up to 7% under the memory limitation constraint at the expense of increased computation. Under the constraint of maintaining the same level of compression ratios, the algorithm reduces the memory usage up to 70%.

We present a technique for compression of shortest paths routing tables for wireless ad hoc networks. The main characteristic of such networks is that geographic location of nodes determines network topology. As opposed to encoding individual node locations, at each node our approach groups the remaining nodes in the network into regions. All shortest paths to nodes in a specific region are routed via the same neighboring node. In this paper, we propose an algorithm for dividing a network field into distinct regions to minimize routing table size while guaranteeing shortest path routes. We show that this problem is NP-hard, propose a heuristic to find efficient solutions, and empirically demonstrate the resulting system performance from the perspective of compression ratio and scalability. In our experiments, routing tables compressed using this technique, require 88.9% to 97.9% less storage than uncompressed tables.In order to achieve energy efficient routing, we propose an augmentation to the original routing mechanism that enables load balancing flexibility along with guaranteed shortest path routing at the expense of larger routing tables. Preliminary experiments estimate 10% lifetime extension of network nodes with a tradeoff of an increase in the size of routing tables. Finally, we propose a compression technique that aims at representing trajectories in a sensing network in a compact manner. This approach relies on trajectory prediction using three weighted Markov models, a local, regional and global one, all of them with context-length equal to one. Finally, we discuss a range of possible applications that rely on the developed prediction and routing models.

Preventing execution of unauthorized software on a given computer plays a pivotal role in system security. The key problem is that although a program at the beginning of its execution can be verified as authentic, while running, its execution flow can be redirected to externally injected malicious code using, for example, a buffer overflow exploit. Existing techniques address this problem by trying to detect the intrusion at run-time or by formally verifying that the software is not prone to a particular attack.We take a radically different approach to this problem. We aim at intrusion prevention as the core technology for enabling secure computing systems. Intrusion prevention systems force an adversary to solve a computationally hard task in order to create a binary that can be executed on a given machine. In this paper, we present an exemplary system--SPEF--a combination of architectural and compilation techniques that ensure software integrity at run-time. SPEF embeds encrypted, processor-specific constraints into each block of instructions at software installation time and then verifies their existence at run-time. Thus, the processor can execute only properly installed programs, which makes installation the only system gate that needs to be protected. We have designed a SPEF prototype based on the ARM instruction set and validated its impact on security and performance using the MediaBench suite of applications.

Engineering change (EC) is a technique that enables a designer to rapidly perform minor specification alternations while minimally resynthesizing only small portions of the specification throughout several levels of design abstraction. In this paper, we introduce the first EC-based synthesis technique for coordinated design optimization in multiple steps. The technique has four phases: optimization region identification, feedback formulation, resynthesis in first step, and finally resynthesis in the second design step. To demonstrate the technique, we focus on behavioral synthesis and transformation, scheduling, and register assignment steps. We developed a generic EC-based approach for design optimization during multiple consecutive synthesis steps. Next, we show how one can use EC to enhance coordinated application of transformations and scheduling, and scheduling and register assignment.

Linear programming (LP) in its many forms has proven to be an indispensable tool for expressing and solving optimization problems in numerous domains. We propose the first set of generic watermarking techniques for integer-LP (ILP). The proof of authorship by watermarking is achieved by introducing additional constraints to limit the solution space and can be used as effective means of intellectual property protection (IPP) and authentication. We classify and analyze the types of constraints in the ILP watermarking domain and show how ILP formulations provide more degrees of freedom for embedding signatures than other existing approaches. To demonstrate the effectiveness of the proposed ILP watermarking techniques, the generic discussion is further concretized using two examples, namely Satisfiability and Scheduling.

With the emergence of software delivery platforms such as Microsoft's .NET, code compression has become one of the core enabling technologies strongly affecting system performance. We present PPMexe - a set of compression mechanisms for executables that explores their syntax and semantics to achieve superior compression rates. The fundament of PPMexe is the generic paradigm of prediction by partial matching (PPM). We combine PPM with two pre-processing steps: instruction rescheduling to improve prediction rates and partitioning of a program binary into streams with high auto-correlation. We improve the traditional PPM algorithm by using: an additional alphabet of frequent variable-length super-symbols extracted from the input stream of fixed-length symbols and a low-overhead mechanism that enables decompression starting from an arbitrary instruction of the executable, a feature pivotal for run-time software delivery. PPMexe was implemented for x86 binaries and tested on several large Microsoft applications. Binaries compressed using PPMexe were 16-23% smaller than files created using PPMD, the best available compressor.

Recently, the Internet revolutionized many activities from entertainment to marketing and business. Two key underlying Internet technologies, efficient data delivery and hypertext, demonstrated exceptional potential as new application enablers. In this paper, we present a novel Hypermedia-Aided Design (HAD) collaboration framework that facilitates new communication and data presentation paradigms to improve the effectiveness of typical EDA applications. The framework leverages on the advantages of using semantic multicast as a communication backbone and quantized hypermedia presentations as an efficient data organization, retrieval, and presentation model. Semantic multicast is a global communication tool that relies on an inter-network of proxies to provide content discovery and semantics-based profile-driven data dissemination services. We introduce the notion of a quant, an atomic interactive multimedia information primitive with embedded hyperlinks. We demonstrate how interest-specific quant retrieval and concatenation can enable more focused collaboration.

Deep submicron technology has two major ramifications on the design process: (i) critical paths are being dominated by global interconnect rather than gate delays and (ii) ultra high levels of integration mandate designs that encompass numerous intra-synchronous blocks with decreased functional granularity and increased communication demands. These factors emphasize the importance of the on-chip bus network as the crucial high-performance enabler for future systems-on-chip. By using independent functional blocks with programmable connectivity, designers are able to build systems-on-chip capable of supporting different applications with exceptional levels of resource sharing. To address challenges in this design paradigm, we have developed a methodology that enables efficient bus network design with approximate timing verification and floorplanning of multi-purpose systems-on-chip in early design stages. The design platform iterates system synthesis and floorplanning to build min-area floorplans that satisfy statistical time constraints of applications. We demonstrate the effectiveness of our bus network design approach using examples from a multimedia benchmark suite.

Deep submicron technology scaling has two major ramifications on the design process. First, reduced feature size significantly increases wire delay, thus resulting in critical paths being dominated by global interconnect rather than gate delays. Second, ultra high level of integration mandates design of systems-on-chip that encompass numerous intra-synchronous blocks with decreased functional granularity and increased communication demands. To address these issues we have developed an on-chip bus network design methodology and corresponding set of tools which, for the first, time, close the synthesis loop between system and physical design. The approach has three components: a communication profiler, a bus network designer, and a fast approximate floorplanner. The communication profiler collects run-time information about the traffic between system cores. The bus network design component optimizes the bus network structure by coordinating information from the other two components. The floorplanner aims at creating a feasible floorplan and to communicate information about the most constrained parts of the network.