Transcript A13

MC# 2.0: a language for concurrent distributed
programming based on .NET
Yury Serdyuk
Program Systems Institute of Russian Academy of Sciences,
Pereslavl-Zalessky, Russia
Contents
1.
2.
3.
4.
5.
Introduction: MC# - a language for .NET-based
concurrent distributed programming.
Novel constructs of MC#: movable methods,
channels, handlers.
Programming in MC#:
- finding prime numbers,
- interaction of distributed processes.
Implementation.
Conclusions.
Introduction
Tools for organizing parallel computations:
- MPI ( for systems with message passing),
- OpenMP (for systems with shared memory)
have been implemented for C and Fortran languages
and hence are
- very low-level and
- inadequate for OO languages like C++,C#,Java.
MPI and OpenMP interfaces rely on the use of
- libraries, rather then on
- appropriate programming language constructs.
Introduction
A modern high-level programming language consist of:
1) basic constructs of the language itself, and
2) a collection of specialized libraries accessible through
appropriate APIs.
A modern tendency to transfer key concepts of most important APIs
into corresponding native constructs of programming languages:
- Polyphonic C# = C# + asynchronous methods
(instead of System.Threading library)
- C = C# + new data type constructors along with query definition
tools
(instead of ADO.NET data subsystem)
Introduction
Next step in this direction:
MC# = C# + high-level constructs for concurrent distributed
programming
(instead of System.Remoting and System.Threading libraries)
Goal of MC# - to replace C and Fortran languages along with MPI and
OpenMP interfaces in the area of industrial concurrent distributed
programs
X10 language (IBM PERCS project – Productive Easy-to-use Reliable
Computer Systems) –
“non-uniform cluster computing”
Introduction
MC# language –
1) there is no need to distribute computational
processes over cluster nodes explicitly,
2) new computational processes can be created and
distributed over accessible nodes during program
execution dynamically,
3) there is no necessity to code by hand an object
(data) serialization / deserialization.
Introduction
MC# language is an adaptation of the basic idea of the
Polyphonic C# language (Benton N., Cardelli L., Fournet
C. – Microsoft Research Laboratory, Cambridge, UK)
for the case of concurrent distributed programming
In Polyphonic C asynchronous methods can be used
either
1) on a single computer, or
2) on a set of machines where they have been fixed and
interact through the remote method calls
Introduction
In MC# language
1) execution of an autonomous asynchronous method
can be scheduled on a different machine selected (in a
typical case) automatically by Runtime-system,
2) interaction of asynchronous methods that are
executed on different machines is implemented using
channels and channel message handlers,
3) channels and handlers are defined using chords in
the Polyphonic C# style.
Introduction
MC# 2.0 :
1) channel message handlers
(instead the bidirectional channels),
2) different semantical treatment of channels
and handlers.
Novel constructs of MC#
In Polyphonic C#, asynchronous methods are intended for playing two major
roles:
1) the role of autonomous methods implementing the basic algorithm and
executed in separate threads, and
2) that of the methods intended for delivering data to conventional,
synchronous methods.
In MC# these two kind of methods form special syntactic categories of
1) movable methods and
2) channels
respectively.
Novel constructs of MC#
In Polyphonic C#
asynchronous methods used for data delivery are
usually declared together with synchronous methods.
In MC#
such synchronous methods form another special
syntactic category of channel message handlers
(or handlers for short).
Movable methods
Writing a parallel program in MC# reduces to labeling by
keyword movable the methods that may be transferred
to other machines for execution:
modifiers movable method_name (arguments) {
< method body >
}
In MC#, movable methods are the only way to create and
run concurrent distributed processes.
Movable methods
The first key feature of MC# language:
in general, during a movable method call, all necessary
data, namely,
1) the object itself to which given movable method
belongs, and
2) arguments for the latter
are only copied (but not moved !) to the remote machine.
Changes made afterwards to the copy will not affect the
original object.
Movable methods
Two modes of parallelizing MC# programs:
- functional: an object for which a movable method is
called, is not transferred to a remote machine,
- nonfunctional: forces the object to be moved to the
remote machine.
These modes are defined by the corresponding modifiers
in the movable method declaration (the default value is
functional ).
Channels and handlers
Channels and handlers are the tools to support the interaction of
distributed objects.
CHandler getInt int ( ) & Channel sendInt ( int x ) {
return ( x );
}
Channels and handlers cannot have a static modifier, and so they are
always bound to some object:
Object
h
c
Channels and handlers
a.sendInt ( x )
- send an integer x by the channel sendInt
A handler is used to receive values from its jointly defined
channel (or group of channels):
int m = a.getInt ()
Channels and handlers
Similarly to Polyphonic C#, it is possible to define several
channels in a single chord:
CHandler equals bool ( ) & Channel c1 ( int x )
& Channel c2 ( int y ) {
if ( x == y )
return ( true );
else return ( false );
}
A general rule for chord triggering:
the body of a chord is executed only after all methods
declared in the chord header have been called.
Channels and handlers
Object
c1
h
c2
An object with a single handler for
multiple channels
Channels and handlers
Object
h1
c1
c2
h2
c3
An object with a “shared” channel
Channels and handlers
The second key feature of MC#:
the channels and handlers can be passed as arguments to the
methods (in particularly, to the movable methods) separately
from the object to which they belong.
Site s
Object a
hs
Site r
(0)
cs
(1)
cs
(2)
Message sending by remote channel:
(0) copying of the channel to remote site,
(1) message sending by (remote) channel,
(2) message redirection to the original site.
Channels and handlers
The third key feature of MC#:
if channels and handlers were copied to a remote site autonomously
or as part of some object, then they become proxy objects
Site s
Object a
hs
Site r
(0)
cs
(4)
hs
(2)
(1)
(3)
Message reading from remote handler:
(0) copying of the handler to remote site,
(1) message reading from (remote) handler,
(2) reading redirection to the original site,
(3)message return from the original site,
(4)result message return.
Programming in MC#
Example - finding prime numbers by the
sieve method
(“Eratosthenes sieve”)
for given a natural number N, enumerate all
primes in the interval from 2 to N.
Eratosthenes sieve
Site i
hin
hin
hin
Sieve
sendPrime
cout
Eratosthenes sieve
Site i
Site i + 1
hin
hin
hin
Sieve
sendPrime
cout
hin
hin
hin
Sieve
cout
Eratosthenes sieve
movable Sieve ( CHandler int() getList,
Channel (int) sendPrime ) {
int p = getList();
sendPrime ( p );
if ( p != -1 ) {
new CSieve().Sieve ( hin, sendPrime );
filter ( p, getList, cout );
}
}
CHandler hin int() & Channel cout ( int x )
{ return ( x ); }
Programming in MC#
Example – an interaction inside a set of distributed
processes in accordance with the “all to all”
principle
class BDChannel {
CHandler Receive object()
& Channel Send (object obj ) {
return ( obj );
}
}
All2all example
DistribProcess1
DistribProcess2
bdc1
Receive Send
bdc2
Receive Send
All2all example
DistribProcess1
bdc1
Receive Send
bdc2
Receive Send
DistribProcess2
bdc1
Receive Send
bdc2
Receive Send
All2all example
class DistribProcess {
movable Start ( int i, … ) {
// i is a process proper number
BDChannel bdc = new BDChannel();
sendBDC ( i, bdc );
BDChannel[] bdchans = (BDChannel[]) bdc.Receive();
// Send messages to other processes
for ( j = 0; j < bdchans.Size; j++ )
if ( j != i )
bdchans[j].Send ( “ … “);
// Receive messages from other processes
for ( j = 0; j < bdchans.Size - 1; j++ )
Console.WriteLine ( (string) bdc.Receive() );
}
}
Implementation
Current implementation based on “bidirectional
channels”:
1) compiler from MC# to C#,
2) Runtime-system.
The compiler’s main function –
to replace movable methods calls by queries to the
Runtime-system which schedules execution for the
methods.
Implementation
Main components of the Runtime-system:
1) Resource Manager – a process implementing
(currently, the simplest) centralized scheduling of
resources (the cluster nodes),
2) WorkNode – a process running on each cluster
node; it’s purpose – to accept the movable methods
scheduled for execution on the given node and to
run them in separate threads
Implementation
Compiler & Runtime-system:
both Windows and Linux versions
.NET for Linux – the Mono system
(www.mono-project.com): a free
implementation of .NET for Unix-like systems
Implementation
MC# applications:
- fractal calculation,
- (simple) 3D rendering,
- radar-tracking signals processing,
- computational molecular dynamics
etc.
Implementation
50,0
45,0
40,0
35,0
30,0
25,0
20,0
15,0
10,0
5,0
0,0
1
2
4
8
12
16
20
24
28
32
Processing time (in sec.) for 40 Mb input file
for radar-tracking signals processing task
The tests were conducted on the “SKIF K-1000” cluster
(98th in Top500, November 2004) of the United Institute of
Informatics Problems, National Academy of Sciences of Belarus
Conclusion
MC# project site - http://u.pereslavl.ru/~vadim/MCSharp
Future work:
1) implementing MC# in full accordance with the ideas
put forward in the given presentation,
2) decentralized scheduling of movable methods calls,
3) providing support for modern fast interconnects
(infiniband),
4) developing MC# programming system for metacluster
computations.