A new parallel algorithm for regular expression matching is developed and applied to the classical grep (global regular expression print) problem. Building on the bitwise data parallelism previously applied to the manual implementation of token scanning in the Parabix XML parser, the new algorithm represents a general solution to the problem of regular expression matching using parallel bit streams. On widely-deployed commodity hardware using 128-bit SSE2 SIMD technology, our algorithm implementations can substantially outperform traditional grep implementations based on NFAs, DFAs or backtracking. 5X or better performance advantage against the best of available competitors is not atypical. The algorithms are also designed to scale with the availability of additional parallel resources such as the wider SIMD facilities (256-bit) of Intel AVX2 or future 512-bit extensions. Our AVX2 implementation showed dramatic reduction in instruction count and significant improvement in speed. Our GPU implementations show further acceleration.

Modern applications employ text files widely for providing data storage in a readable format for applications ranging from database systems to mobile phones. Traditional text processing tools are built around a byte-at-a-time sequential processing model that introduces significant branch and cache miss penalties. Recent work has explored an alternative, transposed representation of text, Parabix (Parallel Bit Streams), to accelerate scanning and parsing using SIMD facilities. This paper advocates and develops Parabix as a general framework and toolkit, describing the software toolchain and run-time support that allows applications to exploit modern SIMD instructions for high performance text processing. The goal is to generalize the techniques to ensure that they apply across a wide variety of applications and architectures. The toolchain enables the application developer to write constructs assuming unbounded character streams and Parabix's code translator generates code based on machine specifics (e.g., SIMD register widths). The general argument in support of Parabix technology is made by a detailed performance and energy study of XML parsing across a range of processor architectures. Parabix exploits intra-core SIMD hardware and demonstrates 2×-7× speedup and 4× improvement in energy efficiency when compared with two widely used conventional software parsers, Expat and Apache-Xerces. SIMD implementations across three generations of x86 processors are studied including the new SandyBridge. The 256-bit AVX technology in Intel SandyBridge is compared with the well established 128-bit SSE technology to analyze the benefits and challenges of 3-operand instruction formats and wider SIMD hardware. Finally, the XML program is partitioned into pipeline stages to demonstrate that thread-level parallelism enables the application to exploit SIMD units scattered across the different cores, achieving improved performance (2× on 4 cores) while maintaining single-threaded energy levels.

Parallel bit stream algorithms exploit the SWAR (SIMD within a register) capabilities of commodity processors in high-performance text processing applications such as UTF-8 to UTF-16 transcoding, XML parsing, string search and regular expression matching. Direct architectural support for these algorithms in future SWAR instruction sets could further increase performance as well as simplifying the programming task. A set of simple SWAR instruction set extensions are proposed for this purpose based on the principle of systematic support for inductive doubling as an algorithmic technique. These extensions are shown to significantly reduce instruction count in core parallel bit stream algorithms, often providing a 3X or better improvement. The extensions are also shown to be useful for SWAR programming in other application areas, including providing a systematic treatment for horizontal operations. An implementation model for these extensions involves relatively simple circuitry added to the operand fetch components in a pipelined processor.

High performance SIMD text processing using the method of parallel bit streams is introduced with a case study of UTF-8 to UTF-16 transcoding. A forward transform converts byte-oriented character stream data into eight parallel bit streams. Decoding, validation and computation of UTF-8 indexed UTF-16 bit streams are performed using bit-parallel logic and shifting operations. Conversion from UTF-8 indexing to UTF-16 indexing is performed using parallel bit deletion. The inverse transform is applied to yield high and low UTF-16 byte streams which are then merged. Combined with optimization techniques for blocks of ASCII data, speed-ups of 3 to 25 times are achieved on commodity processors compared with optimized byte-at-a-time code. Further applications of the method of parallel bit streams to bulk text processing applications are briefly discussed along with future prospects for the combination of intraregister and intrachip parallelism on multicore processors.

Although mobile code systems typically employ link-time code verifiers to protect host computers from potentially malicious code, implementation flaws in the verifiers may still leave the host system vulnerable to attack. Compounding the inherent complexity of the verification algorithms themselves, the need to support lazy, dynamic linking in mobile code systems typically leads to architectures that exhibit strong interdependencies between the loader, the verifier, and the linker. To simplify verifier construction and provide improved assurances of verifier integrity, we propose a modular architecture based on the concept of proof linking. This architecture encapsulates the verification process and removes dependencies between the loader, the verifier, and the linker. We also formally model the process of proof linking and establish properties to which correct implementations must conform. As an example, we instantiate our architecture for the problem of Java bytecode verification and assess the correctness of this instantiation. Finally, we briefly discuss alternative mobile code verification architectures enabled by the proof-linking concept.

Security flaws are routinely discovered in commercial implementations of mobile code systems such as the Java Virtual Machine (JVM). Typical architectures for such systems exhibit complex interdependencies between the loader, the verifier, and the linker, making them difficult to craft, validate, and maintain. This reveals a software engineering challenge that is common to all mobile code systems in which a static verification phase is introduced before dynamic linking. In such systems, one has to articulate how loading, verification, and linking interact with each other, and how the three processes should be organized to address various security issues.We propose a standard architecture for crafting mobile code verifiers, based on the concept of proof linking. This architecture modularizes the verification process and isolates the dependencies among the loader, verifier, and linker. We also formalize the process of proof linking and establish properties to which correct implementations must conform. As an example, we instantiate our architecture for the problem of Java bytecode verification and assess the correctness of this instantiation. Finally, we briefly discuss alternative mobile code verification architectures enabled by our modularization.

A good structure is an important quality aspect of a program. Well-structured, modular programs are less costly to maintain than unstructured monolithic ones. Quantitatively assessing structure and modularity of programs can be useful to help ensure that a program is well-structured by indicating a potential need for restructuring of poorly structured code. However, previous structure metrics do not sufficiently account for the modular features used in modern, object-oriented programming languages. We propose four novel measures to assess the modular structure of a software project. Our measures are based on the principle of vocabulary hiding and measure a form of cohesion. A metrics prototype tool has been implemented for the Modula-3 programming language. Informal tests suggest that they are indeed useful to assess the quality of the program structure.>

Maintaining software often requires repetitive and error prone manipulations of source code, particularly when changes must be propagated across many modules. Practical program manipulation tools can alleviate these problems by automatically making changes throughout a program. Such tools can become even more valuable when they allow for manipulation in-the-large: the systematic modification of all the modules that comprise a software project. We demonstrate this concept with two prototype tools. An inter-module renamer locates and renames all and only appropriate instances of an identifier throughout a project, ensuring that no conflicts arise. An inter-module reorganizer automates the task of moving program entities between modules such that import/export declarations are properly updated for modules dependent on the moved entity and for items on which the moved entity is dependent. Our tools are designed for modern block-structured and object-oriented languages such as Modula-3.>

Abstract Pattern matching in modern functional programming languages is tied to the representation of data. Unfortunately, this is incompatible with the philosophy of abstract data types. Two proposals have been made to generalize pattern matching to a broader class of types. The laws mechanism of Miranda allows pattern matching with non-free algebraic data types. More recently, Wadler proposed the concept of views as a more general solution, making it possible to define arbitrary mappings between a physical implementation and a view supporting pattern matching. Originally, it was intended to include views in the new standard lazy functional programming language Haskell. Laws and views each offer important advantages, particularly with respect to data abstraction. However, if not used with great care, they also introduce serious problems in equational reasoning. As a result, laws have been removed from Miranda and views were not included in the final version of Haskell. We propose a third approach which unifies the laws and views mechanisms while avoiding their problems. Philosophically, we view pattern matching as a bundling of case recognition and component selection functions instead of a method for inverting data construction. This can be achieved by removing the implied equivalence between data constructors and pattern constructors. In practice, we allow automatic mapping into a view but not out of the view. We show that equational reasoning can still be used with the resulting system. In fact, equational reasoning is easier, since there are fewer hidden traps.

The design of procedural and object-oriented programming languages is considered with respect to how easily programs written in those languages can be formally manipulated. Current procedural languages such as Pascal, Modula-2 and Ada; generally support such program manipulations, except for some annoying anomalies and special cases. Three main areas of language design are identified as being of concern from a manipulation viewpoint: the interface between concrete and abstract syntax; the relationship between the abstract syntax and static semantics naming, scoping and typing; and the ability to express basic transformations (folding and unfolding). Design principles are suggested so that the problems identified for current languages can be avoided in the future.>

Accumulators are proposed as a new type of high-level iteration construct for imperative languages. Accumulators are user-programmed mechanisms for successively combining a sequence of values into a single result value. The accumulated result can either be a simple numeric value such as the sum of a series or a data structure such as a list. Accumulators naturally complement constructs that allow iteration through user-programmed sequences of values such as the iterators of CLU and the generators of Alphard. A practical design for high-level iteration is illustrated by way of an extension to Modula-2 called Modula Plus. The extension incorporates both a redesigned mechanism for iterators as well as the accumulator design. Several applications are illustrated including both numeric and data structure accumulation. It is shown that the design supports efficient iteration both because it is amenable to implementation via in-line coding and because it allows high-level iteration concepts to be implemented as encapsulations of efficient low-level manipulations.

Deals with a specific metaprogramming technique which is useful in the maintenance of data-driven software. Data-driven software includes programs whose algorithms are controlled by tables of data, such as table-driven parsers. A maintenance metaprogram for such software must have the ability to inspect and process both the program source code as well as the data tables developed by the software at run time. The easiest way to make the data tables available to the maintenance metaprogram is to run the original program until the data tables are developed in memory. Control is then passed to the maintenance metaprogram, which inspects these tables and the source code of the original program to carry out the maintenance operations. In essence, this involves the construction of a hybrid cross between the original program and the maintenance metaprogram. A case study is considered in which the introspection technique was used in maintenance of a metaprogramming system.>

The use of syntactic information source models for the source encoding (data compression) of messages is described. Syntactic models formulated using context-free grammars augmented with derivation step probabilities are considered. Using an arithmetic coder as the low-level encoding unit, it is shown how practical encoding systems can be constructed from such models. Application of the techniques to the encoding of syntactically correct Pascal computer programs is described, and additional techniques including the use of symbol tables are introduced. The resultant syntactic encoders achieve compression of Pascal programs approaching 90%.>

A metaprogramming system is a programming facility (subprogramming system or language) whose basic data objects include the programs and program fragments of some particular programming language, known as the target language of the system.Such systems are designed to facilitate the writing of metaprograms, that is, programs about programs.Metaprograms take as input programs and fragments in the target language, perform various operations on them, and possibly generate modified target-language programs as output.A grammar-based approach to the specification of the syntactic-manipulation component of a metaprogramming system is described.The method derives the specifications for a set of programmanipulating subprograms from an augmented BNF grammar for the target language.The method is applicable to any programming language and is illustrated in its particular application to Pascal.

Two general classes of machines for performing code translation and serialization are considered;namely Translate-Table and State machines. The Translate-Table machine is a conventional two-stage machine comprising a translation stage folowed by a serialization stage. Two kinds of State machines are examined: 1) counter-driven and 2) microprogrammed.