A Simulation-Based Analysis for Worst Case Delay of Single and Multiple Interruptions
スポンサーリンク
概要
- 論文の詳細を見る
This paper proposes an efficient method to analyze the worst case interruption delay (WCID) of a workload running on modern microprocessors using a cycle accurate simulator (CAS). Our method is highly accurate because it simulates all possible cases inserting an interruption just before the retirement of every instruction executed in a workload. It is also (reasonably) efficient because it takes O(N log N) time for a workload with N executed instructions instead of O(N2) of a straightforward iterative simulation of interrupted executions. The key idea for the efficiency is that a pair of executions with different interruption points has a set of durations in which they behave exactly coherent and thus one of simulations for the durations may be omitted. We implemented this method modifying the SimpleScalar tool set to prove it finds out WCID of workloads with five million executed instructions in reasonable time less than 30 minutes which would be 200-300 days by the straightforward method. Furthermore our CAS-based analyzer may have a post process to calculate the WCID for multiple F interrupts with O(FN√N log N) time complexity.
- 一般社団法人情報処理学会の論文
- 2008-08-27
著者
-
Nagamochi Hiroshi
Kyoto Univ.
-
Hiroshi Nakashima
ACCMS, Kyoto University
-
Takashi Nakada
Nara Institute Of Science And Technology
-
Hiroshi Nakashima
Kyoto University
-
Masahiro Konishi
PFU Ltd.
関連論文
- Constant Time Generation of Trees with Degree Bounds
- A Memory-Efficient Algorithm and Its Implementation of Variable-Size All-to-All Communication
- k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph
- Augmenting Edge-Connectivity and Vertex-Connectivity Simultaneously
- Enumerating Colored and Rooted Outerplanar Graphs
- BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(the 50th Anniversary of the Operations Research Society of Japan)
- APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(the 50th Anniversary of the Operations Research Society of Japan)
- An Efficient Vector Transfer for Sparse Matrix-Vector Multiplication on Distributed Memory Systems
- Orthogonal Drawings for Plane Graphs with Specified Face Areas
- Efficient Representation of Constraints and Propagation of Variable-Value Symmetries in Distributed Constraint Reasoning
- Symmetry Breaking by Dominance Detection in Distributed Environments
- A Light Bypass Network Design for Cascading ALU Executions
- Around the Constructive Orbit Problem in Distributed Constraint Programming
- The Next-to-Shortest Path in Undirected Graphs with Nonnegative Weights
- FOREWORD (Special Section on Discrete Mathematics and Its Applications)
- GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(Network Design, Control and Optimization)
- Accelerating A* algorithms by sweeping out small-degree nodes
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS
- A Simulation-Based Analysis for Worst Case Delay of Single and Multiple Interruptions
- Multilingualization Based on RPC for Job-level Parallel Script Language, Xcrypt
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- Breadth-first Search Approach to Enumeration of Tree-like Chemical Compounds
- CONSTANT FACTOR APPROXIMATION ALGORITHMS FOR REPETITIVE ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS