For Avtar2008 Only Tutorial for Project VII
kpecet
simulating_the_dynix.doc3
1
Simulating the DYNIX Operating System Parallel Programming Interface on a UNIX System
Published in: Journal Software—Practice & Experience Volume 28 Number 5, 1998
SUMMARY
This paper presents the implementation of multitasking functions of DYNIX Sequent computers on the UNIX operating system. The Sequent computers are shared memory multiprocessor computers running the DYNIX operating system. These functions support data and function partitioning. They let the user implement subprograms by the processors of a Sequent computer in parallel. The functions can synchronize, lock, and unlock data and program segments. As a result, the simulator allows the users develop their multitasking programs on a uniprocessor computer such as a Sun work station and later port them to a Sequent computer. Further, the simulator adds a level of abstraction on top of UNIX for concurrent programming. The functions of the simulator allow the user to handle the communication and synchronization of the processes in a program at a higher level of abstraction while concentrating on the design of multitasking algorithms. The simulator is applied to a parallel selection algorithm.
KEY WORDS: DYNIX, Sequent computer, Parallel programming, Concurrent programming.
INTRODUCTION
A parallel program consists of a set of tasks cooperating to achieve a common goal. Typically, tasks communicate by exchanging messages or updating shared memory. Many of the recent multiprocessors have been based on shared memory architectures. For example, the CRAY X-MP1, Alliant2, BBN Butterfly3, and Sequent4 multiprocessors are all based on shared memory. The Sequent Symmetry is a shared-address-space computer that runs the DYNIX operating system, a multiprocessor version of UNIX. The entire main memory is equally accessible to all processors. This model consists of n physical processors running n UNIX processes, which may be assigned to execute n tasks in a parallel application. The tasks can share data and communicate with each other through shared memory. The Sequent Computer is programmed in languages such as ISO/ANSI-standard C, C++, Fortran, and Pascal. These languages include extensions that allow programs to specify explicit parallelism. The DYNIX Parallel Programming Library provides multitasking routines and functions to allocate shared memory. The multitasking routines are of two kinds: the function partitioning and the data partitioning or microtasking routines. These functions assign processors to execute tasks in parallel, identify individual tasks, suspend tasks during sequential program sections, impose mutual exclusion on shared data, and synchronize the tasks4, 5. This paper explains how to simulate these functions using the C language on a UNIX system. The goal of this paper is to facilitate the design and implementation of parallel algorithms for two classes of programmers: those who do not have convenient access to a Sequent computer and those who plan to design concurrent programs for UNIX. The first group can design their algorithms, program them for a Sequent computer, and implement them with the simulator. Once a program works, they can transfer it to an actual Sequent computer. By using process management UNIX system calls such as fork, signal, and wait, the program becomes obscure and error prone. To avoid such problems, the second group can use the functions of the simulator to design a more efficient, structured, and modular program. Therefore, the simulator adds a higher level of abstraction to UNIX multitasking programming. For example, UNIX system calls such as fork, wait, and signal have been used to simulate Dataflow graphs6, but applying the three classes of DYNIX functions will produce a more elegant, efficient implementation. An application program such as implementation of a class of Two-Level grammars using LL(1)-based parsing7 has been implemented with the programming language Occam8, using message passing technique. A more extensive class of this formalism such as Dynamic Semantic Specification by Two-Level Grammar for a Block Structured Language with Subroutine Parameters9 can be implemented by the simulator using shared memory.
The following section describes the role of a preprocessor in the simulator. The preprocessor adds several function calls and changes some of the declarations. The next three sections describe and define the simulation of microtasking, function partitioning, and shared memory allocation routines. The paper also presents a parallel program for a selection algorithm10 by applying some of these functions. The paper assumes the reader is somewhat familiar with the UNIX system calls11,12.
THE SIMULATOR PREPROCESSOR
The simulator has a preprocessor that adds the following to any parallel program:
A. A function named initialize is inserted as the first statement to function main. The initialize function creates a number of shared variables and semaphores to be used in other functions of the simulator. The concept of semaphore was first defined by Dijkstra13, 14. A semaphore, sem, is a nonnegative integer variable that can only be changed or tested by one of two indivisible routines:
p(sem):
if (sem > 0) decrement sem
else wait until sem becomes nonzero.
v(sem):
if some processes are waiting on this semaphore,
restart one of them
else increment sem by one.
In the simulators, a semaphore variable sem is created as a pipe, and the operations p and v are “read from” and “write to” the pipe sem, respectively. However, it is possible to use the semaphore operations of UNIX. The initialize function also has several calls to the UNIX system call signal, such that, upon any run time error, the simulator can safely remove the shared variables from the system.
B. A function, named clean, is added as the last statement to function main. Clean removes all the shared variables from the system. This is necessary. Otherwise, the successive execution of other parallel programs will fail.
C. Declaration of variables, such as, shared sbarrier_t bp and shared slock_t lp for a Sequent computer are changed to shared sbarrier_t bp=NULL and shared slock_t lp = NULL respectively. This helps the simulator to find out whether or not a barrier bp or a lock lp has been initialized. A NULL value for bp or lp means they have not been initialized.
D. Calls such as s_init_barrier(bp) and s_init_lock(lp) in C language for Sequent are changed to s_init_barrier(&bp) and s_init_lock(&lp), respectively. This change initializes bp and lp after the call.
E. A call to setjmp(*position) is added prior to any call to m_multi(). This makes child processes call the function longjmp(*position, 1) to jump over a program segment that should only be executed by the parent. Therefore, all processes, including the parent, will be synchronized after the statement m_multi(). The variable position points to a shared data location and all the processes can have access to this shared location through the variable position. Similarly, a call to setjmp(*pos), where pos is a different shared variable, is inserted prior to any call to m_rele_procs().
THE MICROTASKING FUNCTIONS
Microtasking, or data partitioning, refers to the parallel execution of a task or iterations of a loop. The microtasking library functions of DYNIX provide the function m_fork to initiate parallel tasks. Therefore, the computing load of a parallel algorithm is divided by the number of processors running in parallel. The processors work on different data, executing the same subprogram. In an application program, the user specifies the number of processors needed with m_set_procs function. For example, in:
m_set_procs(7);
m_fork(search, s, a);
where search is a function and s and a are its arguments, the system sets seven processors, each executing search(s, a). Other functions are available to control data flow and synchronize the tasks at different points in the program. Since most likely these tasks share some data, there are functions to impose mutual exclusion for accessing shared data locations. Syntax and semantics of these functions are explained below.
1. m_fork(function_name, arg1, arg2..., argn)
void function_name();
The function m_fork executes the function function_name(arg1, arg2..., argn).
2. m_get_myid()
m_get_myid returns task identification number, which has been assigned to each task by a call to m_fork. These numbers are 0, 1, 2, … , and they are different from process identification number created by UNIX system call fork in the simulator.
3. m_get_numprocs()
The function m_get_numprocs returns the value of a shared variable m_numprocs, the number of processors set in the program. For example, if the system has thirty processors, and the application program is set to use only ten processors, then the value of m_numprocs is 10.
4. m_kill_procs()
This function terminates the child processes created by a call to m_fork.
5. m_lock() and m_unlock()
These functions lock and unlock a lock, respectively. The function m_lock and m_unlock mark the beginning and end of the shared data, respectively. Controlling access to shared data requires the ability to synchronize operations on the shared data, and to access the data in mutual exclusion. These functions are provided to ensure that shared data are accessed in an orderly manner, and to guarantee mutual exclusion.
6. m_next()
M_next increments a shared variable and returns its new value. The function can be used by each task to determine which portion of a shared data structure should be processed next.
7. m_park_procs() and m_rele_procs()
The function m_park_procs suspends child processes. All child processes wait on a semaphore by executing a p operation. The function m_rele_procs resumes execution of child processes. They all execute a v operation on a semaphore.
8. m_set_procs(int n)
m_set_procs sets n processors to be used by m_fork. This number should be less than the number of CPUs in the system.
9. m_single() and m_multi()
m_single blocks all child processes at a barrier. The parent process executes some code following m_single and calls m_multi. At this point, all processes execute the code after m_multi.
10. m_sync()
This function synchronizes all processes at the point of this call.
The following describes the simulation of these functions.
1. A. The function m_fork(function_name, arg1, arg2..., argn)
m_fork creates a number of processes, all of which execute the function call function_name(arg1, arg2..., argn) in parallel. The number of child processes can be set by a call to m_set_procs. However, this number cannot exceed the number of processors of the actual computer. The default number of the processes is “number of CPUs on-line/2". M_fork gives a new identification number to each process. These numbers are different from those created by UNIX system call fork. Here, the parent identification number is zero. The first child’s identification number is 1, the second is 2, and so on. Each process can call the function m_getmyid to obtain its new identification number. The following is a C-like algorithm for m_fork in the simulator.
void m_fork(function_name, arg1, arg2..., argn)
{ ......
......
for (i = 1; i < *m_numprocs; i++)
if (pids[0] == getpid())
if (fork() == 0) {
pids[i] = getpid();
function_name(arg1, arg2..., argn);
v(child_sem);
while(1)
if(park[i]){
p(park_sem);
park[i] = 0;
longjmp(*pos, 1);
}
}
function_name(arg1, arg2..., argn);
for (j = 1; j < *m_numprocs; j++)
p(child_sem);
*child_running = 0;
*m_fork_is_active = 0;
}
The variable pids is a shared array that holds the identification number of the processes created by UNIX system call fork. This array can be accessed by all processes, by calling get_myid, to obtain their new identification number, which is one of the indices of shared array pids. The element pids[0] is already defined in the initialize function by the statement pids[0] = getpid(). This statement is not placed before the for loop, because the user may not call m_fork, yet still use the DYNIX identification number of the parent, which is 0. That is why pids[0] is assigned in the initialize function.
In m_fork, the first loop creates a number of child processes, stores their UNIX identification numbers in pids[1], pids[2], and so on. The parent and each child process executes function_name(arg1, arg2..., argn). The semaphore variable child_sem is used to synchronize the parent and the children. The parent waits on this semaphore in the second loop until all the children complete their jobs. At this time every child cycles on the while loop, and the parent returns to the caller of m_fork. If the user program calls m_park_procs, each child process waits on the semaphore park_sem.
B. The function m_get_myid()
When a process calls m_get_myid, it has a UNIX identification number. The function m_get_myid searches for this number in the shared array pids, finds it, and returns its location as the identification number that has been assigned to this process by m_fork.
C. The functions m_set_numprocs(n) and m_get_numprocs()
The first function sets shared variable *m_numprocs to n. This is done by the parent process, before creating the child processes. The second function is called by any process and it returns the value *m_numprocs. Every call of m_get_numprocs returns the number of child processes set by a prior call of m_set_numprocs(). This number is less than the number of processors in the system.
D. The function m_kill_procs()
Every iteration of the first loop is executed by one of the children, while the parent is waiting on the second loop for all children to terminate.
for (i = 1; i < *m_numprocs; i++)
if (pids[i] != 0)
kill(pids[i], SIGKILL);
for (i = 1; i < *m_numprocs; i++) wait((int *) 0);
E. The functions m_lock() and m_unlock()
Any process calling m_lock executes the statement p(m_lock_sem), where m_lock_sem is a semaphore and its initial value is one. After the first process acquires the lock, the others wait on this semaphore to get the lock. The first process can release the lock by a call to m_unlock to execute the statement v(m_lock_sem). Note that in this and the following sections, any variable preceded by the word sem is a semaphore variable defined in the simulator.
F. The function m_next()
In the function initialize, a shared variable *global_counter is created and assigned to 0. The function m_next simply increments this variable and returns its value. This function is accessible by all the processes.
G. The functions m_park_procs(), m_rele_procs(), m_single(), and m_multi()
In a program these m_park_procs and m_rele_procs are called in the following format:
m_fork(function_name,...);
m_park_procs();
program segment
m_rele_procs();
The simulator preprocessor changes these to:
m_fork(function_name,...);
m_park_procs();
program segment
setjmp(*pos);
m_rele_procs();
When m_fork returns, all the child processes are cycling on the while loop described in part A. That is:
while(1)
if(park[i]){
p(park_sem);
park[i] = 0;
longjmp(*pos, 1);
}
This is a “busy waiting loop” because all the elements of the shared array park are already assigned to zero in the function initialize. The function m_park_procs changes the content of this array to one. At this time all the child processes execute the operation p(park_sem), waiting on the semaphore park_sem.
The function m_rele_procs executes the operation v(park_sem), n times, for n child processes. At this time, these processes are released. Then, the child processes reinitialize the shared array park to zero and jump to the statement after setjmp(*pos). Although the child processes also call m_rele_procs, the execution of v(park_sem) in this function is conditional and is in the form of:
if (m_get_myid() == 0)
v(park_sem);
Therefore, the parent process, not the child processes, executes the v operation. Implementation of the functions m_single and m_multi is similar to the one of m_park_procs and m_rele_procs, respectively. The difference is that the function m_park_procs and m_rele_procs are called after a call to m_fork, whereas the functions m_single and m_multi are called during a call to m_fork. The exact code for these two functions is shown below. The variables *turn, *position, *m_single_is_active, and pids are shared variables. The variables m_single_sem, and parent_wait_sem are semaphore variables. Note how the simulator stops the parent from progress until all the children wait on semaphore m_single_sem.
void idle_process()
{
*turn = *turn ‑ 1;
if (*turn == 1) v(parent_wait_sem);
p(m_single_sem);
longjmp(*position, 1);
}
void m_single()
{
*m_single_is_active = 1;
if (m_get_myid() == 0) {
*turn = m_get_numprocs();
p(parent_wait_sem);
}
else idle_process();
}
void m_multi()
{ int i, num_child_procs;
if (pids[0] == getpid()) {
num_child_procs = m_get_numprocs() ‑ 1;
for (i = 1; i <= num_child_procs; i++)
v(m_single_sem);
*m_single_is_active = 0;
}
}
H. The function m_sync()
The idea is that all the processes, including the parent, should be synchronized at the point that m_sync is called. The semaphore m_sync_sem is used in the function m_sync to synchronize the processes. The variable m_sync_mutex is a semaphore for the purpose of mutual exclusion among the processes. In the initialize function, this variable has already been initialized to one. Except the last process, the others will wait on this semaphore variable. It is the last one that releases them by executing the for loop. The shared variable *last_sync is assigned to the number of processes in the function m_fork. Each process, except the last one, counts down this variable and waits on semaphore m_sync_sem. The last process executes the else part of the if statement of this function and releases all the waiting processes. The last statement in the function m_sync reinitializes the semaphore m_sync_mutex to one.
In order to prevent multiple processes from altering the variable *last_sync at the same time, the simulator uses the semaphore m_sync_mutex to mutually exclude processes from entering this critical section. In fact some of the other functions in the simulator also have critical sections, and the simulator uses the same policy for them.
void m_sync()
{ int i;
........Code for error checking......
p(m_sync_mutex);
if (*last_sync != 1) {
*last_sync = *last_sync ‑ 1;
v(m_sync_mutex);
p(m_sync_sem);
*last_sync = *last_sync + 1;
}
else
for (i = 1; i < *m_numprocs; i++) v(m_sync_sem);
if(*last_sync == *m_numprocs) v(m_sync_mutex);
}
THE FUNCTION PARTITIONING ROUTINES
Function partitioning is a programming technique that allows a single program to be partitioned into multiple interrelated tasks executed on a uniprocessor or multiprocessor computer. Here the computation model consists of multiple processes, created by the UNIX system call fork, and assigning a different task for each process. This technique in the Sequent computer, and therefore the simulator, is achieved by adding function calls in the original program to provide proper linkage, synchronization and mutual exclusion of the tasks. The syntax and the semantics of these functions are described below.
1. cpus_online()
Returns the number of the processors.
2. s_init_lock(slock_t lp), s_lock(slock_t lp), s_clock(slock_t lp), and s_unlock(slock_t lp).
The function s_init_lock initializes a lock. After the lock is initialized, a call to either functions s_lock or s_clock locks the lock on the shared variable lp. The type slock_t is actually a shared unsigned char. The variable lp behaves like a binary semaphore. If the lock is not free, a call of s_lock by a process makes the process wait until the lock is free, whereas a call to s_clock in this situation does not make the caller wait. A call to function s_unlock releases the lock. Since an application can declare different variables like lp, there is no limit to the number of locks. Each lock lp implements a critical section that is mutually exclusive by inserting s_lock and s_unlock before and after the section, respectively. Therefore, it is possible to have several critical sections with different locks that do not interfere with one another.
3. s_init_barrier(sbarrier_t bp, int n) and s_wait_barrier(sbarrier_t bp)
A barrier synchronizes several processes at a specific point in an application. A barrier is a reusable place of rendezvous for the processes. The function s_init_barrier initializes a barrier for n processes. A call to function s_wait_barrier by any process makes the process wait until exactly n processes have arrived and called s_wait_barrier. At this point all n processes are released simultaneously. The variable bp is a shared data structure of type sbarrier_t.
A. The function cpus_online()
This function returns a constant value for the number of processors in the system. If the user is merely using the simulator as an abstract multiprocessing system in UNIX, he can change this constant value in order to serve his needs. However, if he is using the simulator to design a parallel program to be transferred to a Sequent computer, then he cannot change this constant value. This is because the number of processors in the computer is fixed and predetermined.
B. The functions s_init_lock(lp), s_lock(lp), and s_clock(lp)
The function s_lock is a named semaphore, whereas m_lock is an unnamed lock. With a call such as s_lock(lp) or s_clock(lp), the user can define a number of locks. A lock is declared by the user as:
shared slock_t lp;
The simulator preprocessor changes this to:
slock_t lp = NULL;
where slock_t is a type name in the simulator defined as:
typedef struct {
int fd_sem[2];
int free;
}lock_type;
typedef lock_type *slock_t;
A call to s_init_lock(lp) creates a space for this structure in shared memory and initializes the semaphore fd_sem to one. It also assigns the field free to one, meaning the lock is free. Creating space in the shared memory for any lock is necessary, as these locks are created by any process and any other process can call s_lock or s_clock. Therefore, locks are shared by all the processes. Note that a call such as:
s_init_lock(lp);
is changed by the preprocessor simulator to:
s_init_lock(&lp);
Therefore, on return from the call, the actual argument lp is pointing to a shared space allocated for the above structure. The main statement in s_lock or s_clock is a p operation on the semaphore of lp. The function s_lock always executes a p operation. Therefore, if the lock is not released, the process calling s_lock(p) waits to acquire the lock. The function s_clock acquires the lock only if it is free. If the lock is not free, the process calling s_clock will not wait. The code for these three functions is listed below. The semaphore s_lock_mutex is already initialized by one in the initialize function, and is used for the purpose of mutual exclusion between processes in the system.
void s_init_lock(slock_t *lp)
{
*lp = (slock_t) shmalloc(sizeof(lock_type));
make_semaphore((*lp)‑>fd_sem, 1);
(*lp)‑>free = 1;
}
int s_lock(slock_t lp)
{
p(s_lock_mutex);
if (lp == NULL)
error_exit("The lock has not been initialized\n");
v(s_lock_mutex);
p(lp‑>fd_sem);
}
int s_clock(slock_t lp)
{
p(s_lock_mutex);
if (lp == NULL)
error_exit("The lock has not been initialized\n");
v(s_lock_mutex);
p(s_lock_mutex);
if (lp ‑> free) {
lp‑>free = 0;
p(lp‑>fd_sem);
v(s_lock_mutex);
return !(L_FAILED);
}
else {
v(s_lock_mutex);
return L_FAILED;
}
}
void s_unlock(slock_t lp)
{
p(s_lock_mutex);
if (lp == NULL)
error_exit("The lock has not been initialized\n");
lp‑>free = 1;
v(lp‑>fd_sem);
v(s_lock_mutex);
}
C. The functions s_init_barrier(bp, n) and s_wait_barrier(bp)
In the simulator, a barrier plays the role of a counting semaphore. The simulator’s preprocessor changes a user’s declaration such as:
shared sbarrier_t bp;
to:
sbarrier_t bp = NULL;
where sbarrier_t is the following type definition:
typedef struct {
int fd_sem[2];
int count;
int nprocs;
int s_init_barrier_is_called;
} barrier_type;
typedef barrier_type *sbarrier_t;
For the similar reason, explained for the function s_init_lock, the preprocessor also changes a call such as:
s_init_barrier(bp, n)
to:
s_init_barrier(&bp, n)
A call such as s_init_barrier(&bp, n) creates space for the above structure in the shared memory pointed to by bp. It initializes the semaphore fd_sem to zero, the field count to one, and nprocs to n. The rendezvous point for n processes is now a point in the program, where the call of s_wait_barrier(bp) occurs. At this point n - 1 processes wait on the semaphore fd_sem of bp by p operation. The nth semaphore then releases all waiting processes by operation v on fd_sem of bp. The code for the functions s_init_barrier and s_wait_barrier are listed below. The semaphore s_wait_barrier_mutex, which is initialized by one in the function initialize, is for the purpose of mutual exclusion between n processes calling the function s_wait_barrier.
void s_init_barrier(sbarrier_t *bp, int nprocs)
{
*bp = (sbarrier_t) shmalloc(sizeof(barrier_type));
make_semaphore((*bp)‑>fd_sem, 0);
(*bp) ‑> count = 1;
(*bp) ‑> nprocs = nprocs;
(*bp)‑>s_init_barrier_is_called = 1;
}
void s_wait_barrier(sbarrier_t bp)
{ int i;
p(s_wait_barrier_mutex);
if (bp == NULL)
error_exit("The barrier has not been initialized\n");
v(s_wait_barrier_mutex);
p(s_wait_barrier_mutex);
if (bp‑>count < bp ‑> nprocs) {
bp ‑> count = bp ‑> count + 1;
v(s_wait_barrier_mutex);
p(bp ‑> fd_sem);
bp ‑> count = bp ‑> count ‑ 1;
}
else
for (i = 1; i <= bp ‑> nprocs ‑ 1; i++) v(bp ‑> fd_sem);
if (bp ‑> count == 1) v(s_wait_barrier_mutex);
}
THE MEMORY ALLOCATION FUNCTIONS
The simulator contains two functions to allocate and deallocate shared memory. These are:
1. char *shmalloc(unsigned size)
Allocates shared memory locations.
2. shfree(char *ptr)
Frees shared memory locations pointed to by ptr.
The UNIX system calls shmget, shmat, and shmdt are used to implement these two functions. For these functions, the function initialize creates a shared integer location pointed by variable key and assigns zero to this location. This function also creates a shared array, named shmids, and initializes it to zero. The array shmids stores the identification numbers of processes created to execute the function function_name of m_fork. The function shmalloc increments the value of shared location pointed by variable key. The value of *key is used as an index for the array shmids to identify the key of the shared memory segments in the UNIX system call shmget. This function calls the system call shmget to create a shared segment. The shared memory segment identification, returned by shmget, is saved in the array element shmids[*key]. However the memory segment created is part of physical memory, and not the process’s logical data that calls the function shmalloc. The value of shmids[*key] is used in the system call shmat to attach this memory segment to the process’s logical data space. The code for the function shmalloc is shown below.
char *shmalloc(unsigned size)
{ int *a;
++(*key);
if((shmids[*key] = shmget(*key, size, IFLAG|WMODE)) == ‑1)
error_exit("Shmget failed");
if((a =(int *)shmat(shmids[*key], (char *)0,0))==(int*) ‑1) error_exit("Shmat failed");
return (char *)a;
}
The function shfree calls the UNIX system call shmdt to detach a shared memory segment from a process’ pointer, pointing to this segment. The variable *key and the array shmids are used in the function clean to remove all the shared memory segments from the system, by calling the UNIX system call shmctl several times. The code of the function clean is shown below. The variable shmidsId is a global variable, and the function initialize stores the shared memory segment identifier of the array shmids into this variable.
void clean()
{ int i, TempKey = *key;
if((shmidsId!=‑1)&&
(shmctl(shmidsId,IPC_RMID,(struct shmid_ds *)0)<0)){
printf("\nERROR: Shmctl failed here‑ bye!\n");
exit(1);
}
for (i = 1; i <= TempKey; i++)
if((shmids[i] != 0)&&
(shmctl(shmids[i],IPC_RMID,(struct shmid_ds *)0)<0)){
printf("\nERROR: Shmctl failed there‑ bye!\n");
exit(1);
}
}
A PARALLEL SELECT ALGORITHM
The purpose of this section is to present a parallel program to select kth smallest element in a list of n elements. The algorithm has been implemented using several UNIX multiprocessing system calls10, such as fork, wait, signal, shmget, and shmat. This parallel algorithm is a slight improvement over the one of Akl15. Suppose the computer has N processors. In the following algorithm, S and T are shared arrays of size n, while ZL, ZE and ZG are shared arrays of size N+1, M is a shared array of size N, and k is a shared integer variable.
Algorithm Parallel_Select(S, k)
Step 1:
Process P1 finds out:
If |S| <= N then sort S and returns the kth element
else Divides S into N lists Ui, where i = 1, 2,...,N,
and assigns each list Ui to a process Pi.
Step 2:
for i = 1 to N do in parallel
Process Pi obtains the (k/|S| * |Ui|)th by a sequential select
algorithm and stores it in M.
Step 3:
Process P1 obtains m, the median of M.
Step 4:
for i = 1 to N do in parallel
Process Pi records the number of the elements of the list Ui that
are less than , equal to, and greater than m in ZLi, ZEi, and ZGi
of the lists ZL, ZE, and ZG respectively.
Step 5:
Process P1 finds out the exact positions, where each process Pi can start writing elements of Ui that are less than, equal to, and greater than m in the list T. This is obtained by replacing ZLi, ZEi, and ZGi by:
i i i
( ZLm, ( ZEm, ( ZLm ,
m=1 m=1 m=1
for 1 ( i ( N, and 0 for ZL0, ZE0, ZG0 respectively.
Step 6:
for i = 1 to N do in parallel
Process Pi stores the elements of Ui that are less than, equal
to, and greater than m in the list T starting at positions
ZLi-1 + 1, ZEi-1 + 1, and ZGi-1 + 1, respectively.
This divides T into arrays L, E, and G:
L is the list of elements a of S such that a < m.
E is the list of elements a of S such that a = m.
G is the list of elements a of S such that a > m.
Step 7:
Process P1 finds out:
if |L| >= k then calls Parallel_Select(L, k)
else if |L| + |E| >= k then returns m
else calls Parallel_Select(G, k-|L|- |E|)
This parallel select, above, is different than Akl’s 15. In his algorithm, all the available processes are not utilized at any given time, whereas in the improved one, all the processes are utilized all the time. In his algorithm, the median of each list Ui is obtained, whereas in the improved one, (k/N * |Ui|)th element of the Ui is obtained. This is due to assumption that the array is partially sorted at the beginning. The algorithm has a running time of O(|S|). The Parallel_Select and the related functions designed for this algorithm use the simulator. Since the purpose of this example is to show the application of the simulator, the function Sequential_Select is not described.
void Step2(int S[], int nx, int k, int n, int M[])
{ int newk, myid, term;
myid = m_get_myid();
newk = myid * nx + 1 + (nx - 1) * k / n;
if (myid == m_get_numprocs() - 1) term = n;
else term = (myid + 1) * nx;
M[myid+1]=Sequential_Select(S, myid *nx+1,myid*nx+term+1, newk);
}
void Step4(int S[],int nx,int n,int ZL[],int ZE[], int ZG[], int m)
{ int myid, term, countZL = 0, countZE = 0, countZG = 0, i;
myid = m_get_myid();
if (myid == m_get_numprocs() - 1) term = n;
else term = (myid + 1) * nx;
for (i = myid * nx + 1; i <= term; i++)
if (S[i] < m) countZL++;
else if (S[i] == m) countZE++;
else countZG++;
for (i = myid + 1; i <= N; i++) {
ZL[i] = ZL[i] + countZL;
ZE[i] = ZE[i] + countZE;
ZG[i] = ZG[i] + countZG;
}
}
void Step6(int S[],int T[],int ZL[],int ZE[],int ZG[],int m,int nx)
{ int myid, i, j, Len, iL = 0, iE = 0, iG = 0, is;
myid = m_get_myid();
i = myid + 1;
Len = (ZL[i] - ZL[i-1]) + (ZE[i] - ZE[i-1]) + (ZG[i] - ZG[i-1]);
is = (i - 1) * nx;
for (j = 1; j <= Len; j++)
if (S[is + j] < m)
T[ZL[i - 1] + 1 + iL++] = S[is + j];
else if (S[is + j] == m)
T[ZE[i - 1] + 1 + iE++] = S[is + j];
else
T[ZG[i - 1] + 1 + iG++] = S[is + j];
}
int Parallel_Select(int S[], int n, int k)
{ int m;
int i, id, nx, newk, il = 0, ie = 0, ig = 0, *Temp;
nx = n/N;
if (n <= N) {
sort(S, 1, n); return S[k];
}
m_fork(Step2, S, nx, k, n, M);
m = Sequential_Select(M, 1, N, (N + 1)/2);
m_fork(Step4, S, nx, n, ZL, ZE, ZG, m);
for (i = 0; i <= N; i++) ZE[i] = ZE[i] + ZL[N];
for (i = 0; i <= N; i++) ZG[i] = ZG[i] + ZE[N];
il = ZL[N]; ie = ZE[N] - ZE[0]; ig = ZG[N] - ZG[0];
m_fork(Step6, S, T, ZL, ZE, ZG, m, nx);
for (i = 0; i <= N; i++) ZL[i] = ZE[i] = ZG[i] = 0;
if (il >= k){
Temp = S; S = SS; SS = Temp;
return(Parallel_Select(S, il, k));
}
else if (il + ie >= k) return(m);
else {
Temp = S; S = SS + il + ie ; T = Temp;
return(Parallel_Select(S, ig, k - il - ie));
}
}
main()
{ int i;
initialize();
S = (int *)shmalloc(Size* sizeof(int));
T = (int *)shmalloc(Size* sizeof(int));
M = (int *)shmalloc((N+1)* sizeof(int));
ZL = (int *)shmalloc((N+1)* sizeof(int));
ZE = (int *)shmalloc((N+1)* sizeof(int));
ZG = (int *)shmalloc((N+1)* sizeof(int));
for (i = 0; i <= N; i++) ZL[i] = ZE[i] = ZG[i] = 0;
getdata();
m_set_procs(N);
printf("The %dth element in Parallel Select = %d\n",
k, Parallel_Select(S, n, k));
m_kill_procs();
clean();
}
CONCLUSION
This paper shows lack of a true multiprocessor computer in academic institutions is not an obstacle in research involving parallel algorithms. The goal of this paper is to implement multitasking, and shared memory allocation routines of DYNIX operating system for UNIX. Since DYNIX is the operating system of Sequent computers, by implementing these routines on UNIX, the user is able to design parallel programs, debug, and execute them on UNIX. Once a program works, the user can transfer it to a Sequent computer with little or no change.
The simulator supports function partitioning by allowing a single application, written in C language, to consist of multiple, closely cooperating processes to execute the same task. The DYNIX simulator is able to allocate and de-allocate memory for shared data, create processes to execute subprograms concurrently, identify individual processes, suspend processes during serial program sections, mutually exclude shared data, and synchronize processes for critical sections. The simulator also lets the user determine the number of CPUs on-line, initialize a lock, lock a lock, unlock a lock, initialize a barrier, and wait at a barrier.
The functions of the simulator allow the programmer to handle the communication and synchronization needs of an algorithm at a higher level than UNIX multiprocessing system calls while concentrating on the design of the concurrent algorithm.
For further insight, one can simulate the parallel library functions of Sequent computer for Fortran and Pascal language. A bigger project would be the hardware simulation of this computer in such a way that DYNIX can be loaded on UNIX systems.
ACKNOWLEDGMENTS
I thank Joanna Couto and the referees for their comments.
REFERENCES
1. The CRAY X-MP Series of Computer Systems, Cray Research, Inc., 1985.
2. Alliant FX/Architecture Manual, Alliant Computer Systems Corp., Littleton, MA, 1989.
3. Butterfly Parallel Processor Overview, BBN Laboratories, 1985.
4. Guide to Parallel Programming on Sequent Computer Systems, Sequent Computer Systems Inc., 1995.
5. A. Osterhaug, Guide to Parallel Programming on Sequent Computer Systems, Englewood Cliffs, NJ: Prentice-Hall, 1989.
6. M. Badii and M. Mahimtura, Dataflow Simulator, Proceedings of Tenth Annual ESCC Conference, October 21-22, 1994.
7. A. J. Fisher, Practical LL(1)-Based Parsing of Van Wijngaarden Grammar, Acta Informatica 21 (1985), 559-584.
8. Inmos Ltd.: Occam Programming Manual. Englewood Cliffs, New Jersey, Prentice-Hall, 1984.
9. M. Badii and F. Abdollahzadeh, Dynamic Semantic Specification by Two-Level Grammar for a Block Structured Language with Subroutine Parameters, ACM Sigplan Notices vol. 28, No. 5, May 1993, 9-18.
10. M. Badii, J. F. Malerba, and N. S. Murthy, A Parallel Algorithm for Selection Sort and Its Implementation in C Using fork() and wait(), proceeding of Twelfth Annual ESCC Conference, October, 25-26, 1996.
11. K. Haviland and B. Salama, UNIX System Programming, Addison-Wesley Publishing Company, Inc., 1987.
12. B. W. Kernighan and R. Pike, The UNIX Programming Environment, Englewood Cliffs, NJ: Prentice-Hall, 1984.
13. E. W. Dijkstra, Hierarchical Ordering of Sequential Processes, Acta Informatica, vol. 1, 115-138, 1971.
14. E. W. Dijkstra, Co-operating Sequential Processes, Programming Language, F. Genuys (ed.), Academic Press, New York, NY, 1968.
15. S. G. Akl, The Design and Analysis of Parallel Algorithms, Englewood Cliffs, NJ: Prentice-Hall, 1989.
