The Experts below are selected from a list of 10710 Experts worldwide ranked by ideXlab platform

Cosmin E Oancea - One of the best experts on this subject based on the ideXlab platform.

  • a lightweight in place implementation for Software Thread level speculation
    ACM Symposium on Parallel Algorithms and Architectures, 2009
    Co-Authors: Cosmin E Oancea, Alan Mycroft, Tim Harris
    Abstract:

    Thread-level speculation (TLS) is a technique that allows parts of a sequential program to be executed in parallel. TLS ensures the parallel program's behaviour remains true to the language's original sequential semantics; for example, allowing multiple iterations of a loop to run in parallel if there are no conflicts between them.Conventional Software-TLS algorithms detect conflicts dynamically. They suffer from a number of problems. TLS implementations can impose large storage overheads caused by buffering speculative work. TLS implementations can offer disappointing scalability, if Threads can only commit speculative work back to the "real" heap sequentially. TLS implementations can be slow because speculative reads must consult look-aside tables to see earlier speculative writes, or because speculative operations replace normal reads and writes with expensive synchronisation primitives (e.g. CAS or memory fences).We present a streamlined Software-TLS algorithm for mostly-parallel loops that aims to avoid these problems. We allow speculative work to be performed in place, so we avoid buffering, and so that reads naturally see earlier writes. We avoid needing a serial-commit protocol. We avoid the need for CAS or memory fences in common operations. We strive to reduce the size of TLS-related conflict-detection state, and to interact well with typical data-cache implementations. We evaluate our implementation on off-the-shelf hardware using seven applications from SciMark2, BYTEmark and JOlden. We achieve an average 77% of the speed-up of manually-parallelized versions of the benchmarks for fully parallel loops. We achieve a maximum of a 5.8x speed-up on an 8-core machine.

  • Software Thread level speculation an optimistic library implementation
    Proceedings of the 1st international workshop on Multicore software engineering, 2008
    Co-Authors: Cosmin E Oancea, Alan Mycroft
    Abstract:

    Software Thread level speculation (TLS) solutions tend to mirror the hardware ones, in the sense that they employ one, exact dependency-tracking mechanism. Our perspective is that Software-flexibility is, perhaps, better exploited by a family of lighter, if less precise speculative models that can be combined together in an effective configuration, which takes advantage of the application's code-patterns. This paper reports on two main contributions. First, it introduces SpLSC: a Software TLS model that trades the potential for false-positive violations for a small memory overhead and efficient implementation. Second, it presents PolyLibTLS: a library that encapsulates several lightweight models and enables their composition. In this context, we report on the template meta-programming techniques that we used to achieve performance and safety, while preserving library's modularity, extensibility and usability properties. Furthermore, we demonstrate that the user-framework interaction is straightforward and present parallelization timing results that validate our high-level perspective.

Tim Harris - One of the best experts on this subject based on the ideXlab platform.

  • a lightweight in place implementation for Software Thread level speculation
    ACM Symposium on Parallel Algorithms and Architectures, 2009
    Co-Authors: Cosmin E Oancea, Alan Mycroft, Tim Harris
    Abstract:

    Thread-level speculation (TLS) is a technique that allows parts of a sequential program to be executed in parallel. TLS ensures the parallel program's behaviour remains true to the language's original sequential semantics; for example, allowing multiple iterations of a loop to run in parallel if there are no conflicts between them.Conventional Software-TLS algorithms detect conflicts dynamically. They suffer from a number of problems. TLS implementations can impose large storage overheads caused by buffering speculative work. TLS implementations can offer disappointing scalability, if Threads can only commit speculative work back to the "real" heap sequentially. TLS implementations can be slow because speculative reads must consult look-aside tables to see earlier speculative writes, or because speculative operations replace normal reads and writes with expensive synchronisation primitives (e.g. CAS or memory fences).We present a streamlined Software-TLS algorithm for mostly-parallel loops that aims to avoid these problems. We allow speculative work to be performed in place, so we avoid buffering, and so that reads naturally see earlier writes. We avoid needing a serial-commit protocol. We avoid the need for CAS or memory fences in common operations. We strive to reduce the size of TLS-related conflict-detection state, and to interact well with typical data-cache implementations. We evaluate our implementation on off-the-shelf hardware using seven applications from SciMark2, BYTEmark and JOlden. We achieve an average 77% of the speed-up of manually-parallelized versions of the benchmarks for fully parallel loops. We achieve a maximum of a 5.8x speed-up on an 8-core machine.

Alexander G Dean - One of the best experts on this subject based on the ideXlab platform.

  • TOSSTI: Saving Time and Energy in TinyOS with Software Thread Integration∗
    2016
    Co-Authors: Zane D. Purvis, Alexander G Dean
    Abstract:

    Many wireless sensor nodes (motes) interface with slow peripheral devices, requiring the processor to wait. These delays waste time, energy and power, which are valu-able but limited resources on many motes. This paper presents techniques to use Software Thread integration (STI) in TinyOS applications to recover the idle time for useful processing. We modify the TOS scheduler to support the se-lection and execution of integrated Threads. We analyze the impact of integration on task response time. We demonstrate these methods by applying them to a microphone array sam-pling application to save computation time and energy. We find that the integrated tasks finish 17.7 % faster, reducing application active time (and hence application energy) by 6.3%. 1

  • Software Thread integration for instruction level parallelism
    ACM Transactions in Embedded Computing Systems, 2013
    Co-Authors: Won So, Alexander G Dean
    Abstract:

    Multimedia applications require a significantly higher level of performance than previous workloads of embedded systems. They have driven digital signal processor (DSP) makers to adopt high-performance architectures like VLIW (Very-Long Instruction Word). Despite many efforts to exploit instruction-level parallelism (ILP) in the application, the speed is a fraction of what it could be, limited by the difficulty of finding enough independent instructions to keep all of the processor's functional units busy. This article proposes Software Thread Integration (STI) for instruction-level parallelism. STI is a Software technique for interleaving multiple Threads of control into a single implicitly multiThreaded one. We use STI to improve the performance on ILP processors by merging parallel procedures into one, increasing the compiler's scope and hence allowing it to create a more efficient instruction schedule. Assuming the parallel procedures are given, we define a methodology for finding the best performing integrated procedure with a minimum compilation time. We quantitatively estimate the performance impact of integration, allowing various integration scenarios to be compared and ranked via profitability analysis. During integration of Threads, different ILP-improving code transformations are selectively applied according to the control structure and the ILP characteristics of the code, driven by interactions with Software pipelining. The estimated profitability is verified and corrected by an iterative compilation approach, compensating for possible estimation inaccuracy. Our modeling methods combined with limited compilation quickly find the best integration scenario without requiring exhaustive integration.

  • Software Thread integration for hardware to Software migration
    2000
    Co-Authors: Alexander G Dean
    Abstract:

    This dissertation introduces Software Thread integration (STI) and its use for migrating functions from hardware to Software (HSM). STI interleaves multiple Software Threads at the assembly language level, offering efficient concurrency for general-purpose processors. This concurrency is invaluable for HSM, which requires concurrent execution of multiple real-time Software Threads. STI provides a set of compiler-implemented code transformations which produce efficient code. Putting the transformations into a compiler lets the system developer work at a higher level and therefore with more efficiency. Existing methods of HSM suffer from a complicated manual process and inefficient output code. Despite these limits, embedded system designers frequently perform HSM to meet design goals. STI provides a mechanism for efficiently sharing the CPU by interleaving multiple real-time Software Threads into an integrated Thread, replacing context switching and busy waiting with useful instructions to raise efficiency. It uses code transformations which can be automated and implemented in a post-pass compiler. This automation lets system developers perform HSM much more efficiently, reducing development time and effort. Timing accuracy, run-time overhead and code size can be traded off to meet a specific embedded system's goals. This dissertation contributes automatic methods for guiding, performing, and evaluating STI and HSM. It begins by presenting the code transformations needed to integrate real-time Threads. These transformations are implemented in a compiler to automate integration and speed migration. The code produced is more efficient than that of other methods and can be optimized for program size or speed. It shows how to measure Thread suitability for integration based upon idle time distribution and segment timing determinacy. It then presents a method to select Threads for integration based upon these metrics and profiling information, and then predict the resulting system performance and memory cost. It introduces methods for linking a trigger event with the execution of service Thread. These methods allow a system designer to trade off efficiency for response latency. Finally, this dissertation also presents other benefits of STI such as concurrent error detection and performance enhancement.

Alan Mycroft - One of the best experts on this subject based on the ideXlab platform.

  • a lightweight in place implementation for Software Thread level speculation
    ACM Symposium on Parallel Algorithms and Architectures, 2009
    Co-Authors: Cosmin E Oancea, Alan Mycroft, Tim Harris
    Abstract:

    Thread-level speculation (TLS) is a technique that allows parts of a sequential program to be executed in parallel. TLS ensures the parallel program's behaviour remains true to the language's original sequential semantics; for example, allowing multiple iterations of a loop to run in parallel if there are no conflicts between them.Conventional Software-TLS algorithms detect conflicts dynamically. They suffer from a number of problems. TLS implementations can impose large storage overheads caused by buffering speculative work. TLS implementations can offer disappointing scalability, if Threads can only commit speculative work back to the "real" heap sequentially. TLS implementations can be slow because speculative reads must consult look-aside tables to see earlier speculative writes, or because speculative operations replace normal reads and writes with expensive synchronisation primitives (e.g. CAS or memory fences).We present a streamlined Software-TLS algorithm for mostly-parallel loops that aims to avoid these problems. We allow speculative work to be performed in place, so we avoid buffering, and so that reads naturally see earlier writes. We avoid needing a serial-commit protocol. We avoid the need for CAS or memory fences in common operations. We strive to reduce the size of TLS-related conflict-detection state, and to interact well with typical data-cache implementations. We evaluate our implementation on off-the-shelf hardware using seven applications from SciMark2, BYTEmark and JOlden. We achieve an average 77% of the speed-up of manually-parallelized versions of the benchmarks for fully parallel loops. We achieve a maximum of a 5.8x speed-up on an 8-core machine.

  • Software Thread level speculation an optimistic library implementation
    Proceedings of the 1st international workshop on Multicore software engineering, 2008
    Co-Authors: Cosmin E Oancea, Alan Mycroft
    Abstract:

    Software Thread level speculation (TLS) solutions tend to mirror the hardware ones, in the sense that they employ one, exact dependency-tracking mechanism. Our perspective is that Software-flexibility is, perhaps, better exploited by a family of lighter, if less precise speculative models that can be combined together in an effective configuration, which takes advantage of the application's code-patterns. This paper reports on two main contributions. First, it introduces SpLSC: a Software TLS model that trades the potential for false-positive violations for a small memory overhead and efficient implementation. Second, it presents PolyLibTLS: a library that encapsulates several lightweight models and enables their composition. In this context, we report on the template meta-programming techniques that we used to achieve performance and safety, while preserving library's modularity, extensibility and usability properties. Furthermore, we demonstrate that the user-framework interaction is straightforward and present parallelization timing results that validate our high-level perspective.

Clark Verbrugge - One of the best experts on this subject based on the ideXlab platform.

  • Software Thread level speculation for the java language and virtual machine environment
    Lecture Notes in Computer Science, 2006
    Co-Authors: Christopher J F Pickett, Clark Verbrugge
    Abstract:

    Thread level speculation (TLS) has shown great promise as a strategy for fine to medium grain automatic parallelisation, and in a hardware context techniques to ensure correct TLS behaviour are now well established. Software and virtual machine TLS designs, however, require adherence to high level language semantics, and this can impose many additional constraints on TLS behaviour, as well as open up new opportunities to exploit language-specific information. We present a detailed design for a Java-specific, Software TLS system that operates at the bytecode level, and fully addresses the problems and requirements imposed by the Java language and VM environment. Using SableSpMT, our research TLS framework, we provide experimental data on the corresponding costs and benefits; we find that exceptions, GC, and dynamic class loading have only a small impact, but that concurrency, native methods, and memory model concerns do play an important role, as does an appropriate, language-specific runtime TLS support system. Full consideration of language and execution semantics is critical to correct and efficient execution of high level TLS designs, and our work here provides a baseline for future Java or Java virtual machine implementations.