What is StackThreads/MP?
StackThreads/MP is a library that supports fine-grain multithreading in
GCC/G++. It is supplied as a set of C library routines that are callable
from any GCC/G++ code that satisfies a few conditions. It supports dynamic
thread migration on multiprocessor systems, assuming cache-coherent shared-memory.
Unlike traditional user-level thread libraries (e.g., Pthreads), it tolerates
a large number of (say, 10,000 or much more) threads and imposes a very
small overhead for creating and terminating a thread. The programmer can
create a new thread of control upon any procedure call and a thread creation
usually adds only a few instructions to the procedure call. StackThreads/MP
thus allows a programming style in which the programmer assigns a thread
to a unit of work that s/he considers natural, and spawns them dynamically
when needed.
The net result is that, using fine-grain threads, you can reduce the cost
of building a parallel program, either from scratch or from an existing
sequential source, and the cost of maintenance. It is also useful as a
compilation target of higher-level parallel programming languages.
HEML document is available here.
Supported Platforms
StackThreads is available on the following platforms (inside parenthesis
are OS versions we used for development. I am not an expert for differences
between OS-versions):
- Solaris (2.5.1) on SPARC processors
- Solaris (2.6) on x86 processors
- Linux (kernel 2.1.115, libc6-2.0.6) on x86 processors
- Linux (kernel 2.2.5) on Alpha processors
- IRIX (6.4) on MIPS processors
- Digital UNIX (4.0) on Alpha processors
- Windows NT on x86 processors (experimental)
For Solaris, I believe any version newer than 2.5 will be OK. Linux is
changing rapidly, so you may have to spend sometime to run it on other
versions (I am not sure at all). For IRIX, I believe any 6.x will be OK.
Not sure about 5.x. For Digitax UNIX, I had some troubles in compiling
the library on version 3.2. The problem appeared to come from obsolete
pthread.h in Digital UNIX 3.2. I believe modifications, if any, will beminor
on UNIXes. I have no experiences on NT multiprocessors.
Requirements
StackThreads assumes the following tools (inside parenthesis are versions
we used).
- GNU C (2.7.2.1, 2.7.2.3, and 2.8.1. b18
on NT)
- GNU awk (3.03, b18 on NT)
- GNU make (3.77, b18 on NT)
GNU C and GNU awk are mandatory. If you don't have any of them, you should
install it. They are widely available. GNU make is somewhat optional, but
Makefiles for the library assume some gmake-specific features. You may
workaround them. On UNIX platforms, it would be nice if you have xgraph.
With xgraph, you have a simple graphical profiler for StackThreads programs.
It is not necessary for building library and your applications. You may
also download patches to gcc
to guarantee safety of programs that use StackThreads library.
gcc 2.8 has a bug in -mflat on SPARC. We don't recommend to use 2.8 anyway, but be sure to apply our patch if you ever like to use gcc 2.8 on SPARC.
- GNU C, GNU awk, and GNU make
- Xgraph
Download
History
- 1999 Jan 23 First release
- 2000 Feb 25 Second release (Alpha Linux support, gcc 2.95 support, bug fixes)
- 2000 Nov 13 StackThreads/MP is adopted at Omni: RWCP OpenMP Compiler Project.
Mailing List
StackThreads/MP mailing list (sthreads@yl.is.s.u-tokyo.ac.jp) is a mailing
list for exchanging information between users and developers. Please join
the list and send questions to this list, so that other users can share
questions and answers, and users can help each other. It is going to be
used also for announcements of future updates. If you are using StackThreads/MP
for any non-trivial task, we encourage you to join the list. Enter your
Email address in the box below and push the button (It is currently managed
manually. Therefore it takes a while to actually register you as a member.
Send a mail to sthreads-author@yl.is.s.u-tokyo.ac.jp when you want to unsubscribe
from the list).
Feedback, please!
StackThreds is not intended to be just a demonstration of research results.
I will do efforts to make StackThreads a tool for serious users. To achieve
this goal, feedback from you is essential. In particular, please, contact
us (sthreads-author@yl.is.s.u-tokyo.ac.jp),
if you made any improvement to StackThreads that you think is useful for
others. Contributions that are welcome include (but are not limited to):
- Report that says it ran on your platform not listed above (please include
CPU, OS, OS-versions). Even minor differences in OS-versions are sometimes
important. Your report will be reflected to the supported platforms list.
- Report that says it did not run on your platform (please include CPU,
OS, OS-versions, and problem descriptions)
- Changes you made to run it on other OS versions
- Changes you made to run it on other operating systems
- Changes you made to run it on other CPUs
- Applications parallelized with StackThreads
- Bug reports
These messages may be sent to StackThreads/MP mailing list as well, if
you like to send them to people in the list. Since our human resource is
severely limited, we cannot guarantee that we will do an effort to port
it on your platform. But if the problem is simple, we will be able to assist
you via Email.
Patches to GCC
Although StackThreads/MP can be practically used with unmodified GCC, there
are certain cases where execution scheme of StackThreads breaks the assumption
that code generator of GCC exploits. These cases are described in the manual.
If you do not want to patch gcc, you can workaround them by hand. If you
want to guarrantee safety, however, we recommend you to apply the following
patch to gcc. The patch is quite small (less than 100 lines). Unless an
explicit option (see below) is given, the patched gcc produces exactly
the same output with the original gcc. When an explicit option is given,
it produces a slightly different code for programs that are otherwise unsafe
(most programs are not affected at all). Of course, code generated with
such explicit options are 100% compatible with code compiled normally.
You can call functions compiled normally from functions compiled with such
explicit options, and vice versa. You can start off just using library
and later apply the patch, if you like the library. The patch is a diff
to gcc 2.7.2.3.
Options this patch adds to GCC are:
- -fcalls-clobber-sp This option tells GCC that a procedure call
may alter SP in an unexpected way. GCC treats stack pointer after a call
as an unknown value. This disables certaion optimizations on i386.
- -mcallee-copies-struct-args (SPARC only) This option tells GCC
that a procedure must copy incoming structure arguments.
Publications
- Yoshizumi Tanaka, Kenjiro Taura, Mitsuhisa Sato, and Akinori Yonezawa.
"Performance Evaluation of OpenMP Applications with Nested Parallelism."
In Proceedings of 5th International Workshop, LCR 2000, May 2000.
(gzipped postscript (letter size),
gzipped postscript (a4))
- Kenjiro Taura, Kunio Tabata, and Akinori
Yonezawa. "Stackthreads/MP : Integrating Futures into Calling
Standards." In Proceedings of ACM SIGPLAN Symposium on
Principles & Practice of Parallel Programming (PPoPP), 1999 (gzipped
postscript (letter size) , gzipped
postscript (a4)).
A fairly comprehensive description of the
architecture of the current release. A shorter version of the technical report below.
- Kenjiro Taura, Kunio Tabata, and Akinori
Yonezawa. "Stackthreads/MP : Integrating Futures into Calling
Standards." Technical Report TR 99-01, University of Tokyo,
February 1999. (gzipped
postscript (letter size) , gzipped
postscript (a4)).
A fairly comprehensive description of the
architecture of the current release. A long version of the PPoPP 99 paper above.
- Kunio Tabata, Kenjiro Taura, and Akinori Yonezawa. "Lazy task
creation for C programs." In IPSJ SIG Notes 97-PRO-14 (Proceedings
of Summer United Workshops on Parallel, Distributed, Cooperative Processing
(SWoPP '97), 1997 (In Japanese) (gzipped
postscript (a4)).
A description of a prototype of the current release.
- Kenjiro Taura and Akinori Yonezawa. "Fine-grain multithreading
with minimal compiler support---a cost effective approach to implementing
efficient multithreading languages." In Proceedings of the 1997
ACM SIGPLAN Conference on Programming Language Design and Implementation,
pages 320--333, 1997 (gzipped
postscript (letter size) , gzipped
postscript (a4)).
A description of a uniprocessor subset of the current release.
- Kenjiro Taura, Satoshi Matsuoka, and Akinori Yonezawa. "StackThreads
: An abstract machine for scheduling fine-grain threads on stock CPUs."
In Proceedings of Workshop on Theory and Practice of Parallel Programming,
number 907 in Lecture Notes on Computer Science, pages 121--136. Springer
Verlag, 1994 (gzipped
postscript (letter size), gzipped
postscript (a4)).
An old paper that tries to achieve the same goal with a different approach.
- Kenjiro Taura, Satoshi Matsuoka, and Akinori Yonezawa. "An
efficient implementation scheme of concurrent object-oriented languages
on stock multicomputers." In Proceedings of the ACM SIGPLAN Symposium
on Principles & Practice of Parallel Programming (PPoPP), pages 218--228,
1993 (gzipped
postscript (letter size), gzipped
postscript (a4)).
describes where did we come from.
Related Research Projects
Related Sites
This research project is conducted as a part of "Advanced Software
Enrichment Project" of Information-technology
Promotion Agency (IPA), Japan
Copyright (c) 1998,1999 by Kenjiro Taura. All rights reserved.
|
StackThreads/MP is adopted at Omni: RWCP OpenMP Compiler Project!
