27069893
Advanced POC model-based Java instruction folding mechanism
Ever since Java was introduced world wide, the execution performance has always been a problem. As one of the solutions, a bytecode instruction folding process for Java processors was developed in a PicoJava model and a Producer, Operator and Consumer (POC) model, but it could not handle certain types of instruction sequences. In this paper, a new instruction folding scheme based on a new, advanced POC model is proposed and demonstrates improvement in bytecode execution. The proposed POC model is able to detect and fold all possible instruction sequence types dynamically in hardware, including a sequence that is separated by other bytecode instructions. SPEC JMV98 benchmark results show that the proposed POC model-based folder can save more than 90% of folding operations. In addition, a design of the proposed POC model-based folding process in hardware is much smaller and more efficient than traditional folding mechanisms.
1021056
A performance perspective on the Active Memory System
Abstract One major problem of using Java in real-time and embedded devices is the non-deterministic turnaround time of dynamic memory management systems (memory allocation and garbage collection). For the allocation, the non-determinism is often contributed by the time to perform searching, splitting, and coalescing. For the garbage collection, the turnaround time is usually determined by the size of the heap, the number of live objects, the number of object collected, and the amount of garbage collected. Even with the current state-of-the-art garbage collectors (generational and incremental schemes), they may or may not guarantee the worst-case latency. Moreover, such schemes often prolong overall garbage collection time. In this paper, the performance analysis of the proposed Active Memory Module (AMM) for embedded systems is presented. Unlike the software counterparts, the AMM can perform a memory allocation in a predictable and bounded fashion (14 cycles). Moreover, it can also yield a bounded sweeping time regardless of the number of live objects or heap size. By utilizing the proposed system, the overall speedup can be as high as 23% compared to the garbage collection system of the JDK 1.2.2 running in classic mode.
18001825
Architectural support for dynamic memory management
Recent advances in software engineering, such as graphical user interfaces and object-oriented programming, have caused applications to become more memory intensive. These applications tend to allocate dynamic memory prolifically. Moreover, automatic dynamic memory reclamation (garbage collection, GC) has become a popular feature in modern programming languages. As a result, the time consumed by dynamic storage management can be up to one-third of the program execution time. This illustrates the need for a high-performance memory management scheme. This paper presents a top-level design and evaluation of the proposed instruction extensions to facilitate heap management.
9645285
Using scratchpad to exploit object locality in Java
Performance of modern computers is tied closely to the effective use of cache because of the continually increasing speed discrepancy between processors and main memory. We demonstrate that generational garbage collection employed by a system with cache and scratchpad memory can take advantage of the locality of small short-lived objects in Java and reduce memory traffic by as much as 20% when compared to a cache-only configuration. Converting half of the cache to scratchpad can be more effective at reducing memory traffic than doubling or even quadrupling the size of the cache for several of the applications in SPECjvm98.
12198410
Scalable hardware-algorithm for mark-sweep garbage collection
The memory-intensive nature of object-oriented languages such as C++ and Java has created the need for high-performance dynamic memory management. Object-oriented applications often generate higher memory intensity in the heap region. Thus, a high-performance memory manager is needed to cope with such applications. As today's VLSI technology advances, it becomes increasingly attractive to map software algorithms such as malloc(), free() and garbage collection into hardware. This paper presents a hardware design of a sweeping function (for mark-and-sweep garbage collection) that fully utilizes the advantages of combinational logic. In our scheme, the bit sweep can detect and sweep the garbage in a constant time. Bit-map marking in software can improve the cache performance and reduce number of page faults; however, it often requires several instructions to perform a single mark. In our scheme, only one hardware instruction is required per mark. Moreover, since the complexity of the sweeping phase is often higher than the marking phase, the garbage collection time may be substantially improved. The hardware complexity of the proposed scheme (bit-sweeper) is O(n), where n represents the size of the bit map.
39527990
FPGA-based reconfigurable computing
9862925
Powers of Asteroidal Triple-free Graphs with Applications
An asteroidal triple is an independent set of three vertices in a graph such that every two of them are joined by a path avoiding the closed neighborhood of the third. Graphs without asteroidal triples are called AT-free graphs. In this paper, we show that every AT-free graph admits a vertex ordering that we call a 2-cocomparability ordering. The new suggested ordering generalizes the cocomparability ordering achievable for cocomparability graphs. According to the property of this ordering, we show that every proper power G (k ≥ 2) of an AT-free graph G is a cocomparability graph. Moreover, we demonstrate that our results can be exploited for algorithmic purposes on AT-free graphs.
17161223
Speculative incoherent cache protocols
Multiprocessing and multithreading are becoming ubiquitous even on single chips. With increasing cache sizes, coherence misses in such systems will account for a larger fraction of all cache misses. As communication latencies increase, this larger fraction of coherence misses will cause significant and increased performance losses. Tuning coherence protocols for specific communication patterns and applications can reduce communication latencies. However, these optimizations increase a protocol's design complexity, making the protocol difficult to verify. A competing approach requires parallel programmers to tune applications to work well with simpler protocols. Speculative execution has successfully improved performance in various scenarios. We propose a new type of load speculation, called coherence decoupling. Coherence decoupling is a microarchitectural mechanism that implements separate protocols for speculative use and for the eventual verification of values. The technique reduces the effect of long communication latencies while mitigating the burdens on the coherence protocol designer and the parallel programmer
4458929
Including Biological Literature Improves Homology Search
Annotating the tremendous amount of sequence information being generated requires accurate automated methods for recognizing homology. Although sequence similarity is only one of many indicators of evolutionary homology, it is often the only one used. Here we find that supplementing sequence similarity with information from biomedical literature is successful in increasing the accuracy of homology search results. We modified the PSI-BLAST algorithm to use literature similarity in each iteration of its database search. The modified algorithm is evaluated and compared to standard PSI-BLAST in searching for homologous proteins. The performance of the modified algorithm achieved 32% recall with 95% precision, while the original one achieved 33% recall with 84% precision; the literature similarity requirement preserved the sensitive characteristic of the PSI-BLAST algorithm while improving the precision.
14086063
A modular eigen subspace scheme for high-dimensional data classification
In this paper, a novel filter-based greedy modular subspace (GMS) technique is proposed to improve the accuracy of high-dimensional data classification. The proposed approach initially divides the whole set of high-dimensional features into several arbitrary number of highly correlated subgroups by performing a greedy correlation matrix reordering transformation for each class. These GMS can be treated as not only a preprocess of GMS filter-based classifiers but also a unique feature extractor to generate a particular feature subspaces for each different class presented in high-dimensional data. The similarity measures are next calculated by projecting the samples into different modular feature subspaces. Finally, a GMS filter-based architecture based on the mean absolute errors criterion is adopted to build a non-linear multi-class classifier. The proposed GMS filter-based classification scheme is developed to find non-linear boundaries of different classes for high-dimensional data. It not only significantly improves the classification accuracy but also dramatically reduces the computational complexity of feature extraction compared with the conventional principal components analysis. Experimental results demonstrate that the proposed GMS feature extraction method suits the GMS filter-based classifier best as a classification preprocess. It significantly improves the precision of high-dimensional data classification.
14591723
A Sliding Window Method for Finding Recently Frequent Itemsets over Online Data Streams
A data stream is a massive unbounded sequence of data elements continuously generated at a rapid rate. Consequently, the knowledge embedded in a data stream is likely to be changed as time goes by. However, most of miming algorithms or frequency approximation algorithms for a data stream do not able to extract the recent change of information in a data stream adaptively. This paper proposes a sliding window method of finding recently frequent itemsets over an online data stream. The size of a window defines a desired life-time of the information of a transaction in a data stream.