检索结果-内蒙古大学图书馆

36th IEEE International Conference on Distributed Computing Systems (ICDCS)

作者： Hauck, Franz J. Domaschka, Joerg Univ Ulm Inst Distributed Syst D-89069 Ulm Germany Univ Ulm Inst Informat Resource Management D-89069 Ulm Germany

ISBN: (纸本)9781509014828

There are several applications for the deterministic execution of software, e.g. replicated systems, test and debugging scenarios. In all cases the execution should lead to the same effects in order to be consistent. Multi-threading is one of the major sources of nondeterminism. Several deterministic scheduling algorithms exist that allow concurrent but deterministic executions despite of arbitrary switching decisions of the underlying system schedulers. We present the novel and flexible Unified deterministic Scheduling algorithm (UDS) for weakly and fully deterministic systems. Compared to existing algorithms, UDS has a broad parameter set that can be (re-)configured even at run-time. Further, we show that many existing algorithms are merely a particular configuration of UDS.

关键词： debugging deterministic execution deterministic multithreading state machine replication

来源：评论

学校读者我要写书评

暂无评论

esDMT: Efficient and Scalable deterministic multithreading Through Memory Isolation 20

esDMT: Efficient and Scalable Deterministic Multithreading T...

引用

20th IEEE International Conference on Parallel and Distributed Systems (ICPADS)

作者： Sun, Jie Liao, Xiaofei Zheng, Long Jin, Hai Zhang, Yu Huazhong Univ Sci & Technol Sch Comp Sci & Technol Cluster & Grid Comp Lab Serv Comp Technol & Syst Lab Wuhan 430074 Peoples R China

ISBN: (纸本)9781479976157

deterministic multithreading (DMT) system is well-known to eliminate the harmful program behaviors caused by nondeterminism, i.e., always proceeding the program execution into the same thread schedule for the same given input. To achieve this goal, two kinds of schedules are enforced by existing DMT systems. 1) A mem-based schedule ensures the determinism with the total order of the shared memory accesses, and 2) A sync-based schedule makes it by only enforcing the total order of the synchronization operations. Mem-schedule achieves full determinism but suffers from prohibitive overhead;while sync-schedule mitigates this overhead but cannot ensure the determinism for the race schedules, i.e., part determinism. Much recent research is devoted to the hybrid schedule combining the determinism of mem-schedule and efficiency of sync-schedule. However, they suffer from the practicability and scalability problems due to the defects of their technical characteristics, such as trace collection in advance and huge schedule memoization. To address the above problem, this paper proposes esDMT, an efficient and scalable DMT system using a new technique of memory isolation. It can improve the efficiency by proceeding the execution of each thread in parallel within its private virtual memory, and defers the determinism guarantee by updating private memory into shared memory in a deterministic order according to deterministic lock algorithm, thus further reducing the overhead of inter-thread waiting. In contrast to the previous hybrid work avoiding the nondeterminism of race schedules offline based on the enormous historical records, our key insight is to eliminate the nondeterminism of race schedules online at runtime. Our experimental results on PARSEC benchmarks show that esDMT eliminates the nondeterminism successfully, almost gains the same performance as the sync-schedule (with <18% slowdown compared with pthread library at most), and manifests good scalability on an 8-core m

关键词： Nondeterminism memory isolation memory commit data race deterministic multithreading

来源：评论

学校读者我要写书评

暂无评论

Accelerated deterministic multithreading for Multichannel Video Decoder

Accelerated Deterministic Multithreading for Multichannel Vi...

引用

36th Annual IEEE International Computer Software and Applications Conference (COMPSAC)

作者： Shin, Youngsam Son, Minyoung Lee, Seungwon Lee, Shihwa Samsung Elect CO LTD Samsung Adv Inst Technol Yongin South Korea

ISBN: (纸本)9780769547367

One of the major challenges in developing applications for multicore systems is dealing with non-deterministic behavior. One solution to making threads deterministic is to control their relative execution order based on their progress. That is, we enforce the threads to be interleaved in an order, and the order is determined by the progress of each thread. In this paper, we introduce an efficient deterministic runtime architecture with a deterministic logical counter and an efficient interleaving technique for deterministic multithreading. As a case study, we implement 24 video decoders on a quad core system using the proposed deterministic runtime system.

关键词： deterministic multithreading Multicore Parallel Programming Embedded System

来源：评论

学校读者我要写书评

暂无评论

Kendo: Efficient deterministic multithreading in Software

Kendo: Efficient Deterministic Multithreading in Software

引用

14th International Conference on Architectural Support for Programming Languages and Operating Systems

作者： Olszewski, Marek Ansel, Jason Amarasinghe, Saman MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

ISBN: (纸本)9781605584065

Although chip-multiprocessors have become the industry standard, developing parallel applications that target them remains a daunting task. Non-determinism, inherent in threaded applications, causes significant challenges for parallel programmers by hindering their ability to create parallel applications with repeatable results. As a consequence, parallel applications are significantly harder to debug, test, and maintain than sequential programs. This paper introduces Kendo: a new software-only system that provides deterministic multithreading of parallel applications. Kendo enforces a deterministic interleaving of lock acquisitions and specially declared non-protected reads through a novel dynamically load-balanced deterministic scheduling algorithm. The algorithm tracks the progress of each thread using performance counters to construct a deterministic logical time that is used to compute an interleaving of shared data accesses that is both deterministic and provides good load balancing. Kendo can run on today's commodity hardware while incurring only a modest performance cost. Experimental results on the SPLASH-2 applications yield a geometric mean overhead of only 16% when running on 4 processors. This low overhead makes it possible to benefit from Kendo even after an application is deployed. Programmers can start using Kendo today to program parallel applications that are easier to develop, debug, and test.

关键词： Design Reliability Performance deterministic multithreading Determinism Parallel Programming Debugging Multicore

来源：评论

学校读者我要写书评

暂无评论

Intention Preservation in deterministic multithreading 8

Intention Preservation in Deterministic Multithreading

引用

8th International Conference on Future Generation Communication and Networking FGCN

作者： Zhao, Wenbing Cleveland State Univ Dept Elect & Comp Engn Cleveland OH 44115 USA

ISBN: (纸本)9781479977802

In this paper, we present an analogy between the race condition resolution in a multithreaded application, and conflict resolution for concurrent updates in collaborative editing applications. We introduce the intention preservation problem in deterministic multithreading for programs with race conditions. We point out that current state-of-the-art deterministic multithreading approaches do not have any mechanism to preserve the intention of a program when it is instrumented for deterministic execution. Furthermore, we propose a solution for intention preservation in deterministic multithreading provided that the unprotected shared variables are primitive types.

关键词： deterministic multithreading race condition collaborative editing intention preservation conflict resolution

来源：评论

学校读者我要写书评

暂无评论

UDS: A Novel and Flexible Scheduling Algorithm for deterministic multithreading 35

UDS: A Novel and Flexible Scheduling Algorithm for Determini...

引用

35th IEEE International Symposium on Reliable Distributed Systems Workshops (SRDSW)

作者： Hauck, Franz J. Habiger, Gerhard Domaschka, Joerg Univ Ulm Inst Distributed Syst D-89069 Ulm Germany Univ Ulm Inst Informat Resource Management D-89069 Ulm Germany

ISBN: (纸本)9781509035137

Active replication requires deterministic execution in each replica in order to keep them consistent. Debugging and testing need deterministic execution in order to avoid data races and "Heisenbugs". Beside input, multi-threading constitutes a major source of nondeterminism. Several deterministic scheduling algorithms exist that allow concurrent but deterministic executions. Yet, these algorithms seem to be very different. Some of them were even developed without knowing the others. In this paper, we present the novel and flexible Unified deterministic Scheduling algorithm (UDS) for weakly and fully deterministic systems. Compared to existing algorithms, UDS has a broader parameter set, allowing for many configurations that can be used to adapt to a given work load. For the first time, UDS defines reconfiguration of a deterministic scheduler at run-time. Further, we informally show that existing algorithms can be imitated by a particular configuration of UDS, demonstrating its importance.

关键词： debugging deterministic execution deterministic multithreading scheduling state machine replication

来源：评论

学校读者我要写书评

暂无评论

Efficient deterministic multithreading through Schedule Relaxation 11

Efficient Deterministic Multithreading through Schedule Rela...

引用

23rd ACM Symposium on Operating Systems Principles (SOSP 2011)

作者： Cui, Heming Wu, Jingyue Gallagher, John Guo, Huayang Yang, Junfeng Columbia Univ Dept Comp Sci New York NY 10027 USA

ISBN: (纸本)9781450309776

deterministic multithreading (DMT) eliminates many pernicious software problems caused by nondeterminism. It works by constraining a program to repeat the same thread interleavings, or schedules, when given same input. Despite much recent research, it remains an open challenge to build both deterministic and efficient DMT systems for general programs on commodity hardware. To deterministically resolve a data race, a DMT system must enforce a deterministic schedule of shared memory accesses, or mem-schedule, which can incur prohibitive overhead. By using schedules consisting only of synchronization operations, or sync-schedule, this overhead can be avoided. However, a sync-schedule is deterministic only for race-free programs, but most programs have races. Our key insight is that races tend to occur only within minor portions of an execution, and a dominant majority of the execution is still race-free. Thus, we can resort to a mem-schedule only for the "racy" portions and enforce a sync-schedule otherwise, combining the efficiency of sync-schedules and the determinism of mem-schedules. We call these combined schedules hybrid schedules. Based on this insight, we have built PEREGRINE, an efficient deterministic multithreading system. When a program first runs on an input, PEREGRINE records an execution trace. It then relaxes this trace into a hybrid schedule and reuses the schedule on future compatible inputs efficiently and deterministically. PEREGRINE further improves efficiency with two new techniques: determinism-preserving slicing to generalize a schedule to more inputs while preserving determinism, and schedule-guided simplification to precisely analyze a program according to a specific schedule. Our evaluation on a diverse set of programs shows that PEREGRINE is deterministic and efficient, and can frequently reuse schedules for half of the evaluated programs.

关键词： deterministic multithreading Program Slicing Program Simplification Symbolic Execution

来源：评论

学校读者我要写书评

暂无评论

Determinism at Standard-Library Level in TM-Based Applications

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 2017年第1期45卷 17-29页

作者： Smiljkovic, Vesna Unsal, Osman Cristal, Adrian Valero, Mateo Barcelona Supercomp Ctr Barcelona Spain Univ Politecn Cataluna Barcelona Spain CSIC Spanish Natl Res Council IIIA Artificial Intelligence Res Inst Barcelona Spain

deterministic execution of a multi-threaded application guarantees that threads access shared memory in the same order and the application gives the same output whenever it runs with the same input parameters. Determinism provides repeatability, which helps programmers in testing and debugging. Additionally, transactional memory (TM) simplifies development of multi-threaded applications so that programmers can use transactions (instead of locks) to synchronize accesses to shared memory. However, transactions that call standard library functions have to be serialized, i.e. to be executed as the only running transactions in the system. The serialization enforces an order of threads execution usually different from the one enforced by a system for deterministic multithreading, which causes deadlocks in the application execution. In this paper, we present DeTrans-lib, the first standard C library that provides deterministic execution of TM-based applications at application and standard-library level. DeTrans-lib avoids deadlocks by performing transaction serialization in deterministic order. We evaluate DeTrans-lib with the benchmarks that invoke a standard C library and perform I/O operations.

关键词： Transactional memory deterministic multithreading Concurrency bugs Standard library Serialization

来源：评论

学校读者我要写书评

暂无评论

Globally Precise-restartable Execution of Parallel Programs 14

Globally Precise-restartable Execution of Parallel Programs

引用

35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

作者： Gupta, Gagan Sridharan, Srinath Sohi, Gurindar S. Univ Wisconsin Madison WI 53706 USA

ISBN: (纸本)9781450327848

Emerging trends in computer design and use are likely to make exceptions, once rare, the norm, especially as the system size grows. Due to exceptions, arising from hardware faults, approximate computing, dynamic resource management, etc., successful and error-free execution of programs may no longer be assured. Yet, designers will want to tolerate the exceptions so that the programs execute completely, efficiently and without external intervention. Modern computers easily handle exceptions in sequential programs, using precise interrupts. But they are ill-equipped to handle exceptions in parallel programs, which are growing in prevalence. In this work we introduce the notion of globally precise-restartable execution of parallel programs, analogous to precise-interruptible execution of sequential programs. We present a software runtime recovery system based on the approach to handle exceptions in suitably-written parallel programs. Qualitative and quantitative analyses show that the proposed system scales with the system size, especially when exceptions are frequent, unlike the conventional checkpoint-and-recovery method.

关键词： Design Experimentation Measurement Performance Reliability deterministic multithreading Precise Exceptions

来源：评论

学校读者我要写书评

暂无评论

Self-optimising Application-agnostic multithreading for Replicated State Machines 39

Self-optimising Application-agnostic Multithreading for Repl...

引用

39th International Symposium on Reliable Distributed Systems (SRDS)

作者： Habiger, Gerhard Hauck, Franz J. Reiser, Hans P. Kostler, Johannes Ulm Univ Ulm Germany Univ Passau Passau Germany

ISBN: (数字)9781728176260

ISBN: (纸本)9781728176260

State-machine replication (SMR) is a well-known approach for fault-tolerant services demanding fast recovery. It is not easy, however, to parallelise SMR in order to exploit modern multicore architectures. Two main approaches have been extensively studied;one focusing on request-level concurrency using prior knowledge, the other utilising application-agnostic and lock-level deterministic scheduling. We show that significant performance improvements for the latter approach require deterministic scheduler configurations to be dynamically adapted to the current application load during runtime. First, we summarise current research on parallel SMR execution. Second, an analysis of obstacles in lock-level deterministic multithreading approaches shows how static scheduler configurations can lead to poor performance when load on the system varies over time. Third, we present a simple yet effective automatic adaptation solution, which provides significantly better overall system behaviour compared to static configurations. This is demonstrated by evaluations using a full system setup.

关键词： State-Machine Replication deterministic multithreading Self-Optimisation Concurrent Execution

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：