43650389
An empirical comparison of priority-queue and event-set implementations
Execution times for a variety of priority-queue implementations are compared under the hold model, showing many to be faster than implicit heaps.
44497725
Simulation of information flow in organizations
The Icarus simulation system is the result of an experiment in embedding small rule-based expert systems into a discrete event simulation environment. The goal of this work is to allow the use of expert systems to model the intelligent behavior of people that are included in the system being simulated. The major problems we have encountered in building the Icarus system have resulted from unexpected and fundamental interactions between expert systems and our discrete event simulation framework. These interactions are the focus of this paper.
17285109
Concurrent operations on priority queues
Among the fastest priority queue implementations, skew heaps have properties that make them particularly suited to concurrent manipulation of shared queues. A concurrent version of the top down implementation of skew heaps can be produced from previously published sequential versions using almost mechanical transformations. This implementation requires O(log n) time to enqueue or dequeue an item, but it allows new operations to begin after only O(1) time on a MIMD machine. Thus, there is potential for significant concurrency when multiple processes share a queue. Applications to problems in graph theory and simulation are discussed in this article.
14105636
Experience with concurrent simulation
We have successfully implemented a concurrent simulator and we report initial speedup measurements for this technique. Our algorithm requires a shared-memory multiprocessor and is appropriate to any discrete-event simulation model. In addition, our algorithm places no constraints on minimum service times or the presence of cycles in the simulation model. Our experimental simulator runs on an Encore Multimax computer and is applicable to closed product-form queueing networks. We have observed speedups of 2.3 for a central-server queueing model using our simulator.
18506033
Evaluation of voting systems
T he recent spate of security issues and allegations of " lost votes " in the U.S. demonstrates the inadequacy of the standards used to evaluate our election systems. The current standards (the FEC Voting Systems Standards) along with the revision being developed by IEEE 1583 (see the article by Deutsch and Berger in last month's Communications) are poor from another perspective: they establish a single pass/fail threshold for all systems, thereby eliminating incentives for existing suppliers to improve their products and rendering the market unattractive to new entrants. Moreover, they fail to precisely define the properties that should be required of a voting system. Instead, the standards rely on specific designs that are more than 15 years old. These legacy designs handicap promising new approaches, such as the various voter-verified printing schemes. New systems are unnecessarily burdened, while their substantial advantages go unrecognized. A set of well-defined properties would encourage the development and commercialization of better voting systems, especially when combined with objective ways to measure performance with respect to those properties. The overall result would then resemble the quantitative federal ratings for automobiles , where features such as vehicle safety and fuel efficiency form a basis for Consumer Reports-style comparative tables. Similarly, specific performance rating guidelines for different aspects of voting systems would provide meaningful metrics upon which system developers could compete. Decision makers, both regulatory and purchasing, would then be free to establish their own minimums for these metrics. Such a rating system can thus cleanly disentangle the development of the technical evaluation process from the various political and regulatory processes. asked the technical community for assistance in determining a new standard. This community is no stranger to the area of voting system properties and standards: a number of authors have tried to characterize requirements , and, in 2002, the Workshop on Election Standards and Technology addressed similar issues. The performance properties for voting systems might include the following: integrity of the votes (both voter verification, " I can check that my vote was captured correctly " and public verification, " anyone can check that all recorded votes were counted correctly "); ballot secrecy (both voter privacy and resistance to vote selling and coercion); robustness (including resistance to denial of service attacks); usability and accuracy (including access for the disabled); and transparency (both of mechanism and election data). The inherent differences in system architectures can be characterized …
42995338
Assembly Language as Object Code
The set of meanings that may be encoded in most object languages is a subset of the meanings that may be encoded in most assembly languages. Careful exploitation of this fact in the design of the SMAL assembly and object language allows the SMAL assembler itself to be used as a linkage editor, thus eliminating the need for an expensive and often misunderstood system program. The SMAL assembler is no more complex than many assemblers in common use today, nor are the relevant aspects of the SMAL language particularly unique.
17269099
Edge detection in ultrasound speckle noise
Presents a statistical approach to edge detection in ultrasound speckle, and uses actual noise statistics to derive an expression for an optimal detection rule. The authors compute the optimal detector for the special case of uncorrelated speckle, and an approximation to the optimal detector for the case when signal-to-noise ratio (SNR) is high. They also discuss a simple sub-optimal detection scheme, and show that its performance is close to that of the optimal uncorrelated speckle detection rule, and surpasses that of the high-SNR approximation except in the case of extremely high SNR, in which case they both perform equally well.<<ETX>>
1963957
Fast and efficient searches for effective optimization-phase sequences
It has long been known that a fixed ordering of optimization phases will not produce the best code for every application. One approach for addressing this phase-ordering problem is to use an evolutionary algorithm to search for a specific sequence of phases for each module or function. While such searches have been shown to produce more efficient code, the approach can be extremely slow because the application is compiled and possibly executed to evaluate each sequence's effectiveness. Consequently, evolutionary or iterative compilation schemes have been promoted for compilation systems targeting embedded applications where meeting strict constraints on execution time, code size, and power consumption is paramount and longer compilation times may be tolerated in the final stage of development, when an application is compiled one last time and embedded in a product. Unfortunately, even for small embedded applications, the search process can take many hours or even days making the approach less attractive to developers. In this paper, we describe two complementary general approaches for achieving faster searches for effective optimization sequences when using a genetic algorithm. The first approach reduces the search time by avoiding unnecessary executions of the application when possible. Results indicate search time reductions of 62%, on average, often reducing searches from hours to minutes. The second approach modifies the search so fewer generations are required to achieve the same results. Measurements show this approach decreases the average number of required generations by 59%. These improvements have the potential for making evolutionary compilation a viable choice for tuning embedded applications.
9647930
Cross-layer adaptive video coding to reduce energy on general-purpose processors
Traditionally, video encoders have been designed assuming that the more redundancy is removed, the better the encoder. However, on current laptops, reducing the compression efficiency of the video encoder by reducing the number of instructions used to perform compression can actually reduce the total energy used to encode and transmit a sequence. The correct balance between computation and compression efficiency may change dynamically, motivating adaptive encoders. At the same time, recent general-purpose processors also employ energy-driven adaptations. For best gains, the adaptations in the hardware and application layers must be coordinated. From a system design viewpoint, this coordination must happen through minimal, well-defined interfaces. This paper develops (1) an adaptive video encoder for general-purpose processors that trades computational complexity for compression efficiency to minimize total system energy, and (2) a method for determining the best configuration for such an encoder when running on a processor that is also adaptive. Our adaptive processor employs recent energy saving techniques of dynamic voltage and frequency scaling and architectural adaptation. Using a detailed simulator, we show that our cross-layer adaptive application algorithm reduces energy significantly, when employed on a fixed or adaptive processor.
11334584
The rapid generation of mutation data matrices from protein sequences
An efficient means for generating mutation data matrices from large numbers of protein sequences is presented here. By means of an approximate peptide-based sequence comparison algorithm, the set sequences are clustered at the 85% identity level. The closest relating pairs of sequences are aligned, and observed amino acid exchanges tallied in a matrix. The raw mutation frequency matrix is processed in a similar way to that described by Dayhoff et al. (1978), and so the resulting matrices may be easily used in current sequence analysis applications, in place of the standard mutation data matrices, which have not been updated for 13 years. The method is fast enough to process the entire SWISS-PROT databank in 20 h on a Sun SPARCstation 1, and is fast enough to generate a matrix from a specific family or class of proteins in minutes. Differences observed between our 250 PAM mutation data matrix and the matrix calculated by Dayhoff et al. are briefly discussed.
14721450
Implementation of a block based neural branch predictor
This paper contributes to a dynamic branch predictor algorithm based on a perceptron in two directions: Firstly, a new block form of computation is introduced that reduces theoretically by half the combinational critical path for computing a prediction. Secondly, implementation in FPGA hardware is fully developed for quantitative comparison purposes. FPGA circuits for a one-cycle block predictor produces 1.7 faster clock rates than a direct implementation of the original perceptron predictor. This faster clock allows to realize predictions with longer history lengths for the same hardware budget.