We describe a novel line-level script identification method. Previous work repurposed an OCR model generating per-character script codes, counted to obtain line-level script identification. This has two shortcomings. First, as a sequence-to-sequence model it is more complex than necessary for the sequence-to-label problem of line script identification. This makes it harder to train and inefficient to run. Second, the counting heuristic may be suboptimal compared to a learned model. Therefore we reframe line script identification as a sequence-to-label problem and solve it using two components, trained end-toend: Encoder and Summarizer. The encoder converts a line image into a feature sequence. The summarizer aggregates the sequence to classify the line. We test various summarizers with identical inception-style convolutional networks as encoders. Experiments on scanned books and photos containing 232 languages in 30 scripts show 16% reduction of script identification error rate compared to the baseline. This improved script identification reduces the character error rate attributable to script misidentification by 33%.

In order to perform meaningful experiments in optimizing compilation and run-time system design, researchers usually rely on a suite of benchmark programs of interest to the optimization technique under consideration. Programs are described as numeric, memory-intensive, concurrent, or object-oriented, based on a qualitative appraisal, in some cases with little justification. We believe it is beneficial to quantify the behaviour of programs with a concise and precisely defined set of metrics, in order to make these intuitive notions of program behaviour more concrete and subject to experimental validation. We therefore define and measure a set of unambiguous, dynamic, robust and architecture-independent metrics that can be used to categorize programs according to their dynamic behaviour in five areas: size, data structure, memory use, concurrency, and polymorphism. A framework computing some of these metrics for Java programs is presented along with specific results demonstrating how to use metric data to understand a program's behaviour, and both guide and evaluate compiler optimizations.

Traditional tracing systems are often limited to recording a fixed set of basic program events. This limitation can frustrate an application or compiler developer who is trying to understand and characterize the complex behavior of software systems such as a Java program running on a Java Virtual Machine. In the past, many developers have resorted to specialized tracing systems that target a particular type of program event. This approach often results in an obscure and poorly documented encoding format which can limit the reuse and sharing of potentially valuable information. To address this problem, we present STEP, a system designed to provide profiler developers with a standard method for encoding general program trace data in a flexible and compact format. The system consists of a trace data definition language along with a compiler and an architecture that simplifies the client interface by encapsulating the details of encoding and interpretation.

Quantitative workload characterization is essential to high performance computer architecture design. Unfortunately, quantitative results are typically hard to interpret, reproduce and compare, due to the staggering amount of detail inherent in modern architecture. Source language, compiler technology target ISA, and micro-architecture, intertwined with system aspects such as memory hierarchy and multitasking regime, all add to the complexity of workload characterization. We propose two simple metrics to characterize program execution: a footprint measures the "size" of a program, and a Unified Prediction profile shows its "complexity". These metrics are architecture-independent, and allow meaningful comparisons of program behavior at a numerical but abstract level. We believe they can provide direction to subsequent, more detailed and costly simulation efforts.

Indirect branch prediction is likely to become increasingly important in the fixture because indirect branches occur more frequently in object-oriented programs. With misprediction rates of around 25% on current processors, indirect branches can incur a significant fraction of branch misprediction overhead even though they remain less frequent than the more predictable conditional branches. We investigate a wide range of two-level predictors dedicated exclusively to indirect branches. Starting with predictors that useful-precision addresses and unlimited tables, we progressively introduce hardware constraints and minimize the loss of predictor performance at each step. For programs from the SPECint95 suite as well as a suite of large C++ applications, a two-level predictor achieves a misprediction rate of 9.8% with a 1 K-entry table and 7.3% with an 8 K-entry table, representing more than a threefold improvement over an ideal BTB. A hybrid predictor further reduces the misprediction rates to 8.98% (1 K) and 5.95% (8 K).

Two-level predictors improve branch prediction accuracy by allowing predictor tables to hold multiple predictions per branch. Unfortunately, the accuracy of such predictors is impaired by two detrimental effects. Capacity misses increase since each branch may occupy many entries, depending on the number of different path histories leading up to the branch. The working set of a given program therefore increases with history length. Similarly, cold start misses increase with history length since the predictor must first store a prediction separately for each history pattern before it can predict branches with that history. We describe a new hybrid predictor architecture, cascaded branch prediction, which can alleviate both of these effects while retaining the superior accuracy of two level predictors. Cascaded predictors dynamically classify and predict easily predicted branches using an inexpensive predictor, preventing insertion of these branches into a more powerful second stage predictor. We show that for path-based indirect branch predictors, cascaded prediction obtains prediction rates equivalent to that of two-level predictors at approximately one fourth the cost. For example, a cascaded predictor with 64+1024 entries achieves the same prediction accuracy as a 4096-entry two-level predictor. Although we have evaluated cascaded prediction only on indirect branches, we believe that it could also improve conditional branch prediction and value prediction.

We study the direct cost of virtual function calls in C++ programs, assuming the standard implementation using virtual function tables. We measure this overhead experimentally for a number of large benchmark programs, using a combination of executable inspection and processor simulation. Our results show that the C++ programs measured spend a median of 5.2% of their time and 3.7% of their instructions in dispatch code. For "all virtuals" versions of the programs, the median overhead rises to 13.7% (13% of the instructions). The "thunk" variant of the virtual function table implementation reduces the overhead by a median of 21% relative to the standard implementation. On future processors, these overheads are likely to increase moderately.

Row displacement dispatch tables implement message dispatching for dynamically-typed languages with a run time overhead of one memory indirection plus an equality test. The technique is similar to virtual function table lookup, which is, however, restricted to statically typed languages like C++. We show how to reduce the space requirements of dispatch tables to approximately the same size as virtual function tables. The scheme is then generalized for multiple inheritance. Experiments on a number of class libraries from five different languages demonstrate that the technique is effective for a broad range of programs. Finally, we discuss optimizations of the row displacement algorithm that allow dispatch table construction of these large samples to take place in a few seconds.

article Free Access Share on Selector table indexing & sparse arrays Author: Karel Driesen View Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 28Issue 10Oct. 1, 1993 pp 259–270https://doi.org/10.1145/167962.165902Published:01 October 1993Publication History 42citation378DownloadsMetricsTotal Citations42Total Downloads378Last 12 Months22Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF