Stephen Pellicer, Guihai Chen, Keith C. C. Chan et al. · IEEE Transactions on NanoBioscience · 2008
The public computer architecture shows promise as a platform for solving fundamental problems in bioinformatics such as global gene sequence alignment and data mining with tools such as the basic local alignment search tool (BLAST). Our implementation of these two problems on the Berkeley open infrastructure for network computing (BOINC) platform demonstrates a runtime reduction factor of 1.15 for sequence alignment and 16.76 for BLAST. While the runtime reduction factor of the global gene sequence alignment application is modest, this value is based on a theoretical sequential runtime extrapolated from the calculation of a smaller problem. Because this runtime is extrapolated from running the calculation in memory, the theoretical sequential runtime would require 37.3 GB of memory on a single system. With this in mind, the BOINC implementation not only offers the reduced runtime, but also the aggregation of the available memory of all participant nodes. If an actual sequential run of the problem were compared, a more drastic reduction in the runtime would be seen due to an additional secondary storage I/O overhead for a practical system. Despite the limitations of the public computer architecture, most notably in communication overhead, it represents a practical platform for grid- and cluster-scale bioinformatics computations today and shows great potential for future implementations.
Cited by 15
Jinguo Zhou, Xiao Xiao, Charles Zhang · 2012
Deterministic replay remains as one of the most effective ways to comprehend concurrent bugs. Existing approaches either maintain the exact shared read-write linkages with a large runtime overhead or use exponential off-line algorithms to search for a feasible interleaved execution. In this paper, we propose Stride, a hybrid solution that records the bounded shared memory access linkages at runtime and infers an equivalent interleaving in polynomial time, under the sequential consistency assumption. The recording scheme eliminates the need for synchronizing the shared read operations, which results in a significant overhead reduction. Comparing to the previous state-of-the-art approach of deterministic replay, Stride reduces, on average, 2.5 times of runtime overhead and produces, on average, 3.88 times smaller logs.
Cited by 5
Duy Doan, Kiyofumi Tanaka · 2017
Time complexity is one of the most important requirements for task scheduling algorithms in real-time embedded systems. In order to satisfy this requirement, Enhanced Virtual Release Advancing (EVRA) algorithm [1] was proposed as an effective algorithm with relatively low runtime overhead to shorten response times in the context of Total Bandwidth Server and Earliest Deadline First algorithms. For further reduction of runtime overhead, hardware implementation of EVRA is designed for effectiveness and applicability to actual real-time systems. The implementation targets an ITRON real-time operating system running on an ARM Cortex-A9 processing core with a field-programmable gate array (FPGA). On an evaluation board, the actual runtime overheads were obtained as the number of cycles taken for the algorithm's execution. Evaluation results show that the maximum additional runtime overhead per tick is reduced by up to 30% compared with that of the original (software) virtual release advancing.
Cited by 0
Mehrfard, H. (Hossein), Labiche, Y. (Yvan) · Carleton University's Institutional Repository (MacOdrum Library, Carleton University) · 2015
Reverse-engineering object interactions from source \ncode can be done through static, dynamic, or hybrid (static plus \ndynamic) analyses. In the latter two, monitoring a program and \ncollecting runtime information translates into some overhead \nduring program execution. Depending on the type of application, \nthe imposed overhead can reduce the precision and accuracy of \nthe reverse-engineered object interactions (the larger the overhead \nthe less precise or accurate the reverse-engineered interactions), \nto such an extent that the reverse-engineered interactions \nmay not be correct, especially when reverse-engineering a multithreaded \nsoftware system. One is therefore seeking an instrumentation \nstrategy as less intrusive as possible. In our past work, we \nshowed that a hybrid approach is one step towards such a solution, \ncompared to a purely dynamic approach, and that there is \nroom for improvements. In this paper, we uncover, in a systematic \nway, other aspects of the dynamic analysis that can be improved \nto further reduce runtime overhead, and study alternative \nsolutions. Our experiments show effective overhead reduction \nthanks to a modified procedure to collect runtime information.
Cited by 0Open access
Yafan Huang, Zhengyang He, Lingda Li et al. · 2023
Soft error rate has been increasing due to the shrinking size of transistors, leading to an elevated risk of catastrophic failures in modern computer systems. Error detection by duplicating instructions (EDDI) is a software-based technique to mitigate soft errors with a low runtime performance overhead and has been widely adopted in many safety- and mission-critical real-time systems such as space applications. However, these systems are commonly sensitive to runtime performance overheads the protection techniques incur. Few studies have investigated the performance of EDDI across various system designs and operational parameters, hence lacking a complete understanding in the literature. In this paper, we conduct comprehensive experiments to study the variation of EDDI runtime performance overhead and characterize the root causes. We find that there exist significant variations in performance overheads of EDDI, due to a few architectural and program-level factors. Based on the findings, we propose two practical techniques FuzzyB and Celer: FuzzyB uses an input searching technique to bound EDDI runtime performance overhead across different inputs for a given program; while Celer reduces EDDI run-time performance overheads using compiler transformation (by 25.08% reduction).
Cited by 2
Rui Li, Xiaoyun Zhi, Jinxin Chi et al. · ArXiv.org · 2025
Large Language Models (LLMs) have become a cornerstone of modern AI, driving breakthroughs in natural language processing and expanding into multimodal jobs involving images, audio, and video. As with most computational software, it is important to distinguish between ordinary runtime performance and startup overhead. Prior research has focused on runtime performance: improving training efficiency and stability. This work focuses instead on the increasingly critical issue of startup overhead in training: the delay before training jobs begin execution. Startup overhead is particularly important in large, industrial-scale LLMs, where failures occur more frequently and multiple teams operate in iterative update-debug cycles. In one of our training clusters, more than 3.5% of GPU time is wasted due to startup overhead alone. In this work, we present the first in-depth characterization of LLM training startup overhead based on real production data. We analyze the components of startup cost, quantify its direct impact, and examine how it scales with job size. These insights motivate the design of Bootseer, a system-level optimization framework that addresses three primary startup bottlenecks: (a) container image loading, (b) runtime dependency installation, and (c) model checkpoint resumption. To mitigate these bottlenecks, Bootseer introduces three techniques: (a) hot block record-and-prefetch, (b) dependency snapshotting, and (c) striped HDFS-FUSE. Bootseer has been deployed in a production environment and evaluated on real LLM training workloads, demonstrating a 50% reduction in startup overhead.
Cited by 0Open access
Yuchong Xie, K. F. Zhang, Yu Liu et al. · arXiv (Cornell University) · 2026
Seed explosion is a fundamental problem in fuzzing seed scheduling, where a fuzzer maintains a huge corpus and fails to choose promising seeds. Existing works focus on seed prioritization but still suffer from seed explosion since corpus size remains huge. We tackle this from a new perspective: corpus reduction, i.e., computing a seed corpus subset. However, corpus reduction could lead to poor seed diversity and large runtime overhead. Prior techniques like cull_queue, AFL-Cmin, and MinSet suffer from poor diversity or prohibitive overhead, making them unsuitable for high-frequency seed scheduling. We propose RandSet, a novel randomized corpus reduction technique that reduces corpus size and yields diverse seed selection simultaneously with minimal overhead. Our key insight is introducing randomness into corpus reduction to enjoy two benefits of a randomized algorithm: randomized output (diverse seed selection) and low runtime cost. Specifically, we formulate corpus reduction as a set cover problem and compute a randomized subset covering all features of the entire corpus. We then schedule seeds from this small, randomized subset rather than the entire corpus, effectively mitigating seed explosion. We implement RandSet on three popular fuzzers: AFL++, LibAFL, and Centipede, and evaluate it on standalone programs, FuzzBench, and Magma. Results show RandSet achieves significantly more diverse seed selection than other reduction techniques, with average subset ratios of 4.03% and 5.99% on standalone and FuzzBench programs. RandSet achieves a 16.58% coverage gain on standalone programs and up to 3.57% on FuzzBench in AFL++, triggers up to 7 more ground-truth bugs than the state-of-the-art on Magma, while introducing only 1.17%-3.93% overhead.
Cited by 0Open access
Mohammad Norouzi, Nicolas Morew, Qamar Ilias et al. · Parallel Computing · 2024
Data-dependence profiling is a program-analysis technique for detecting parallelism opportunities in sequential programs. It captures data dependences that actually occur during program execution, filtering parallelism-preventing dependences that purely static methods assume only because they lack critical runtime information, such as the values of pointers and array indices. Profiling, however, suffers from high runtime overhead. In our earlier work, we accelerated data-dependence profiling by excluding polyhedral loops that can be handled statically using certain compilers and eliminating scalar variables that create statically-identifiable data dependences. In this paper, we combine the two methods and integrate them into DiscoPoP, a data-dependence profiler and parallelism discovery tool. Additionally, we detect reduction patterns statically and unify the three static analyses with the DiscoPoP framework to significantly diminish the profiling overhead and for a wider range of programs. We have evaluated our unified approaches with 49 benchmarks from three benchmark suites and two computer simulation applications. The evaluation results show that our approach reports fewer false positive and negative data dependences than the original data-dependence profiler and reduces the profiling time by at least 43%, with a median reduction of 76% across all programs. Also, we identify 40% of reduction cases statically and eliminate the associated profiling overhead for these cases.
Cited by 0Open access
Yuchong Xie, K. F. Zhang, Yu Liu et al. · arXiv (Cornell University) · 2026
Seed explosion is a fundamental problem in fuzzing seed scheduling, where a fuzzer maintains a huge corpus and fails to choose promising seeds. Existing works focus on seed prioritization but still suffer from seed explosion since corpus size remains huge. We tackle this from a new perspective: corpus reduction, i.e., computing a seed corpus subset. However, corpus reduction could lead to poor seed diversity and large runtime overhead. Prior techniques like cull_queue, AFL-Cmin, and MinSet suffer from poor diversity or prohibitive overhead, making them unsuitable for high-frequency seed scheduling. We propose RandSet, a novel randomized corpus reduction technique that reduces corpus size and yields diverse seed selection simultaneously with minimal overhead. Our key insight is introducing randomness into corpus reduction to enjoy two benefits of a randomized algorithm: randomized output (diverse seed selection) and low runtime cost. Specifically, we formulate corpus reduction as a set cover problem and compute a randomized subset covering all features of the entire corpus. We then schedule seeds from this small, randomized subset rather than the entire corpus, effectively mitigating seed explosion. We implement RandSet on three popular fuzzers: AFL++, LibAFL, and Centipede, and evaluate it on standalone programs, FuzzBench, and Magma. Results show RandSet achieves significantly more diverse seed selection than other reduction techniques, with average subset ratios of 4.03% and 5.99% on standalone and FuzzBench programs. RandSet achieves a 16.58% coverage gain on standalone programs and up to 3.57% on FuzzBench in AFL++, triggers up to 7 more ground-truth bugs than the state-of-the-art on Magma, while introducing only 1.17%-3.93% overhead.
Cited by 0Open access
Michael J. Zastre, R. Nigel Horspool · 2005
Abstract. Two new optimizations using whole-program analysis are presented for languages usingtry-catch exceptions clauses (such as Java and C#) – farhandlers reduce the time needed to locate the handler for a thrown exception, and throwsite reduction eliminates unnecessary runtime overhead at throw instructions. Also presented are experimental results from a Java VM modified to implement these optimizations. 1
Cited by 0
Mariuxi Vinueza-Morales, Miguel Tupac-Yupanqui, Nicolás Márquez et al. · Computers · 2026
Speculative parallelization has been proposed to accelerate computationally intensive reasoning tasks in constraint-based systems, particularly minimal conflict detection and preferred diagnosis computation. Parallel variants of QUICKXPLAIN enable concurrent conflict detection, while parallel FASTDIAG supports speculative diagnosis computation. Existing evaluations of these approaches primarily emphasize runtime reduction and speedup metrics. However, runtime alone does not fully characterize computational efficiency in multi-core environments, where synchronization overhead and speculative execution costs may significantly influence performance. This paper introduces a unified multi-dimensional cost model for analyzing speculative parallel conflict detection and diagnosis algorithms. Rather than proposing new algorithms, we reinterpret previously reported experimental results under a formal cost perspective integrating runtime, speedup, efficiency, parallel overhead, and conflict-normalized cost metrics. Our analysis reveals that speculative parallelization provides substantial benefits in high-cardinality conflict scenarios and complex diagnosis tasks, but scalability is limited by coordination overhead and diminishing efficiency as the number of parallel workers increases. We further identify parallel breakdown points beyond which additional workers degrade performance. The proposed framework offers a systematic basis for cost-aware evaluation of parallel reasoning strategies and provides practical insights into when parallelization is beneficial for conflict detection and diagnosis tasks in large-scale constraint systems.
Cited by 0Open access
Brad Peterson, Harish Kumar Dasari, Alan Humphrey et al. · 2015
The Uintah computational framework is used for the parallel solution of partial differential equations on adaptive mesh refinement grids using modern supercomputers. Uintah is structured with an application layer and a separate runtime system. The Uintah runtime system is based on a distributed directed acyclic graph (DAG) of computational tasks, with a task scheduler that efficiently schedules and execute these tasks on both CPU cores and on-node accelerators. The runtime system identifies task dependencies, creates a taskgraph prior to an iteration based on these dependencies, prepares data for tasks, automatically generates MPI message tags, and manages data after task computation. Managing tasks for accelerators pose significant challenges over their CPU task counterparts due to supporting more memory regions, API call latency, memory bandwidth concerns, and the added complexity of development. These challenges are greatest when tasks compute within a few milliseconds, especially those that have stencil based computations that involve halo data, have little reuse of data, and/or require many computational variables. Current and emerging heterogeneous architectures necessitate addressing these challenges within Uintah. This work is not designed to improve performance of existing tasks, but rather reduce runtime overhead to allow developers writing short-lived computational tasks to utilize Uintah in a heterogeneous environment. This work analyzes an initial approach for managing accelerator tasks alongside existing CPU tasks within Uintah. The principal contribution of this work is to identify and address inefficiencies that arise when mapping tasks onto the GPU, to implement new schemes to reduce runtime system overhead, to introduce new features that allow for more tasks to leverage on-node accelerators, and to show overhead reduction results from these improvements.
Cited by 8
Swarup Kumar Sahoo, Man-Lap Li, Pradeep Ramachandran et al. · 2008
In the near future, hardware is expected to become increasingly vulnerable to faults due to continuously decreasing feature size. Software-level symptoms have previously been used to detect permanent hardware faults. However, they can not detect a small fraction of faults, which may lead to Silent Data Corruptions(SDCs). In this paper, we present a system that uses invariants to improve the coverage and latency of existing detection techniques for permanent faults. The basic idea is to use training inputs to create likely invariants based on value ranges of selected program variables and then use them to identify faults at runtime. Likely invariants, however, can have false positives which makes them challenging to use for permanent faults. We use our on-line diagnosis framework for detecting false positives at runtime and limit the number of false positives to keep the associated overhead minimal. Experimental results using microarchitecture level fault injections in full-system simulation show 28.6% reduction in the number of undetected faults and 74.2% reduction in the number of SDCs over existing techniques, with reasonable overhead for checking code.
Cited by 128
Jeffrey K. Hollingsworth · IEEE Transactions on Parallel and Distributed Systems · 1998
We introduce a runtime, nontrace-based algorithm to compute the critical path profile of the execution of message passing and shared-memory parallel programs. Our algorithm permits starting or stopping the critical path computation during program execution and reporting intermediate values. We also present an online algorithm to compute a variant of critical path, called critical path zeroing, that measures the reduction in application execution time that improving a selected procedure will have. Finally, we present a brief case study to quantify the runtime overhead of our algorithm and to show that online critical path profiling can be used to find program bottlenecks.
Cited by 51
Igor Koropiecki, Krzysztof Piotrowski · 2026
One of major challenges in deploying IoT systems to energy-constrained environments is ensuring reliable monitoring and debugging. Addressing this challenge requires tools that impose minimal overhead while still providing meaningful insights. This paper presents a comparative evaluation and overhead analysis of a low-intrusive tool designed for debugging custom low-power nodes during different lifecycle stages. The evaluated tool prioritizes minimal interruption and negligible performance degradation, in attempt to ensure the same runtime conditions for both debugging and final deployments. The tool reduces overhead by 72% in clock cycles and lowers memory usage, when compared to direct UART logging. This reduction translates to extended battery life and reduced environmental impact from battery replacements in long-term deployments.
Cited by 0
Farzad Samie, Vasileios Tsoutsouras, Dimosthenis Masouros et al. · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2019
In the emerging paradigm of edge computing (EC) for Internet of Things (IoT), data processing is pushed to the edge of the IoT network (e.g., gateways and embedded IoT devices). IoT devices must support multiple operation modes in order to adapt to varying runtime situations, like preserving energy at low battery, while still maintaining some crucial functionality, etc. Adapting the optimal operation mode is a challenge for edge devices given the limited resources at the edge of the network (both bandwidth and processing power of the shared gateway), various constraints (e.g., battery lifetime), etc. This paper proposes a fast and low-overhead scheme to determine and adapt the operation mode of edge devices at runtime and orchestrate devices in a way that the efficiency of IoT devices is optimized with respect to the gateway's resource constraints. The proposed scheme breaks the optimization problem into several smaller ones (i.e., subproblems) whose solutions are aggregated to find the final solution. We present a novel memoization technique that determines the solution to a range of subproblems based on subproblems that are already solved. In addition, we present a novel pruning technique that reduces the search space and consequently reduces both memory and execution time overhead. The experimental results show up to 50% reduction in memory overhead and 14× reduction in execution time overhead compared to the state-of-the-art solution which is a major step toward efficient EC for IoT.
Cited by 10
Martino Ciaperoni, Athanasios Katsamanis, Aristides Gionis et al. · Research at the University of Copenhagen (University of Copenhagen) · 2024
A capacity to recognize speech offline eliminates privacy concerns and the need for an internet connection. Despite efforts to reduce the memory demands of speech recognition systems, these demands remain formidable and thus popular tools such as Kaldi run best via cloud computing. The key bottleneck arises form the fact that a bedrock of such tools, the Viterbi algorithm, requires memory that grows linearly with utterance length even when contained via beam search. A recent recasting of the Viterbi algorithm, SIEVE, eliminates the path length factor from space complexity, but with a significant practical runtime overhead. In this paper, we develop a variant of SIEVE that lessens this runtime overhead via beam search, retains the decoding quality of standard beam search, and waives its linearly growing memory bottleneck. This space-complexity reduction is orthogonal to decoding quality and complementary to memory savings in model representation and training.
Cited by 0Open access
Zhuoli Wang, Lei Chen, Shuo Wang et al. · 2024
With the wide application of SRAM-base FPGA in aerospace engineering, the radiation resistance performance of FPGAs becomes unprecedented important. To correct errors, the Triple Modular Redundancy (TMR) technique uses a voter and incurs significant PPA overhead. We propose an efficient in-place soft error mitigation method, that can mitigate soft errors without any additional PPA overhead. Compared to other synthesis-based algorithms, our method uses an XGBoost-based prediction model which predicts time-consuming circuit metrics. For the EPFL benchmark circuit, our approach achieves up to 19.42% runtime speedup, and under 3% loss on the failure rate reduction.
Cited by 1
Jon Brandvein, Yanhong A. Liu · 2016
Powerful optimizations of object queries can lead to reduced asymptotic running times. However, such queries are often used in dynamic languages, and the required generality of the optimizations in handling a dynamic language can lead to significant runtime overhead as well as significantly increased code size. This paper studies combinations of optimizations for reducing this runtime overhead and code size. We describe two new optimizations --- counting elimination and result set elimination, their effectiveness when combined with inlining and when using specialized data structures, and additional optimizations enabled by type analysis and alias analysis. The two new optimizations are enabled by the high-level nature of queries, even though they are difficult and not supported by general compiler optimizations. We have run a variety of benchmarks, including distributed algorithms and benchmarks from prior best systems, obtaining a speedup of up to 56% and code size reduction of up to 37%.
Cited by 2
Wyatt Spear, Allen Malony, Nicholas Chaimov · 2025
This paper investigates an extension of the measurement capabilities of the TAU performance analysis system to support real-time configuration and control. Active performance measurement introduces the ability to include and exclude timers, timer groups, and MPI ranks at runtime based on runtime logic, triggers, and user input. We examine the benefits of these capabilities with respect to instrumentation overhead, data reduction, and analytical focus. We present and evaluate profile and trace results from the Quicksilver and LULESH2.0 proxy apps, executed on the Frontier and Perlmutter supercomputers, respectively. Additional use cases are outlined and control methodologies described for further development of active measurement capabilities in TAU.
Cited by 0