A High Level Multi-Threaded Extension to a Statistical Computing Environment

  1. Abstract

  2. Introduction

    1. What are threads and their history? Contrast with multi-tasking operating systems. Java
    2. Why are we studying threads and how can they be used?
      • Higher level language making multi-threading more accessible
      • motivation from GUIs and logically separate tasks within an application,
      • remote debugging mechanism and monitoring capabilities.
      • multi-processor and performance in the era of intensive computation for statistical problem solving (e.g. bootstrapping, cross-validation, hierarchical models, Markov process simulations) and increased volume of data.
      • modular software development.
      • single user action, but many system (S) actions, such as updating graphics displays (no backing store), etc.
    3. The challenges associated with using threads - synchronization, portability.
      1. General Examples and Examples in S (assignment of entire object x[i] <- 1).
      2. Atomic actions
    4. Purpose of the work.
      • provide low level primitives in a high level language which can be employed to provide higher level interfaces. Tools for programmers/developers.
      • Allow large scale software to be written on top of a statistical language rather than interfacing to it.
      • Still complicated to use threads but greatly simplified.
    5. Special problems and benefits associated with threading a functional (absence of pointers) mathematical/statistical and interactive programming language that supports object persistence.
  3. S User level Thread Application Programming Interface (API)

    1. Modifications to the S Evaluation and Session model

      • The S Evaluation Model, Tasks, Frames and Databases
      • Thread specific inter-task frames.
      • Session specific inter-thread frame.
      • Interface (single or multiple prompt(s)), history mechanism (.Audit file).
    2. S Level Functions

      1. Creating and destroying threads and Thread Attributes.
      2. Inter and Intra thread control. Suspending, canceling tasks.
      3. Synchronization across threads
        • Locking objects and commands, and locking based on values of objects.
        • Reader-writer locks, barriers implemented in terms of the S level primitives in the API.
      4. Changes and simplifications to S functions and classes - readers and timers.
      5. Extended Examples - Data server, Help daemon via a GUI, image matching via maximal correlations computed in parallel.
  4. Internal Design and Implementation

    1. Evaluator Manager
      • Control
      • Messages
      • Monitoring tools.
    2. Thread Locking Databases.
    3. Different Levels of threading and extensibility -
      1. single processor - Pthreads,
      2. multi-processors - Kernel Level Threads (LinuxThreads),
      3. distributed processors
    4. Implementation details of the different levels of threading above.
    5. Other requirements - re-entrant library routines.
    6. Portability.
    7. Other approaches - S engine level scheduling and complications.
  5. Partial Automatic Synchronization via S

    1. Idea of recursively parsing expressions as objects to identify the shared values as input and output variable sets. Then
    2. Contrast with Compiler based parallelization.
    3. Reference to GUI material and callback parsing. Automatic help facility.
    4. Useful prototyping environment for developing parallel algorithms that can be translated to lower-level languages after verification of the correctness of the approach.
  6. Comments and Conclusions

    1. Why can this be considered a statistical thesis?
      • Only high level interactive statistical/mathematical language of which I am aware that offers threads.
      • Makes parallel and distributed processing available to statisticians in an accessible way. Helps to make parallel computing a more viable avenue for more statistical problems.
      • Statistics is becoming increasingly more computer oriented, both in solving the problems and providing software for others to use statistical procedures. This work provides tools for both.
    2. Generalizability to other languages, thread interfaces, etc.
    3. State of the work.
      1. Databases and class mechanism controlled by "servers"
  1. Bibliography

  2. Appendix


Duncan Temple Lang<duncan@stat.Berkeley.EDU>
Last modified: Fri May 30 14:38:34 PDT 1997