Origin2000 Posix Threads Version
authorMilind Bhandarkar <milind@cs.uiuc.edu>
Wed, 26 Nov 1997 19:13:58 +0000 (19:13 +0000)
committerMilind Bhandarkar <milind@cs.uiuc.edu>
Wed, 26 Nov 1997 19:13:58 +0000 (19:13 +0000)
src/arch/origin-pthreads/conv-mach.csh [new file with mode: 0755]
src/arch/origin-pthreads/conv-mach.h [new file with mode: 0644]
src/arch/origin-pthreads/machine.c [new file with mode: 0644]
src/arch/origin-pthreads/spantree.c [new file with mode: 0644]

diff --git a/src/arch/origin-pthreads/conv-mach.csh b/src/arch/origin-pthreads/conv-mach.csh
new file mode 100755 (executable)
index 0000000..f2f9b6d
--- /dev/null
@@ -0,0 +1,48 @@
+############################################################################
+# RCS INFORMATION:
+#
+#      $RCSfile$
+#      $Author$        $Locker$                $State$
+#      $Revision$      $Date$
+#
+############################################################################
+# DESCRIPTION:
+#
+############################################################################
+# REVISION HISTORY:
+#
+#
+############################################################################
+
+set CMK_CPP_CHARM='/usr/lib/cpp '
+set CMK_CPP_C='cc -E -64 '
+set CMK_LDRO='ld -r -o'
+set CMK_LDRO_WORKS=0
+set CMK_CC='cc  -64 '
+set CMK_CC_RELIABLE='cc  -64 '
+set CMK_CC_FASTEST='cc  -64 '
+set CMK_CXX='CC -64 '
+set CMK_CXXPP='CC -E -64 '
+set CMK_CF77=''
+set CMK_C_DEBUG='-g'
+set CMK_C_OPTIMIZE='-O'
+set CMK_CXX_DEBUG='-g'
+set CMK_CXX_OPTIMIZE='-O'
+set CMK_LD='cc -64 '
+set CMK_LDXX='CC -64 '
+set CMK_LD77=''
+set CMK_M4='m4'
+set CMK_SUF='o'
+set CMK_AR='ar cq'
+set CMK_RANLIB='true'
+set CMK_LIBS=' -lqt -lpthread '
+set CMK_SEQ_LIBS=' '
+set CMK_SEQ_CC='cc -64 '
+set CMK_SEQ_LD='cc -64 '
+set CMK_SEQ_CXX='CC -64 '
+set CMK_SEQ_LDXX='CC -64 '
+set CMK_NM='nm'
+set CMK_NM_FILTER="grep '|GLOB |' | sed -e 's/.*|//'"
+set CMK_CPP_SUFFIX="i"
+set CMK_XLATPP='charmxlat++ -w '
+set CMK_QT='origin'
diff --git a/src/arch/origin-pthreads/conv-mach.h b/src/arch/origin-pthreads/conv-mach.h
new file mode 100644 (file)
index 0000000..6f81b21
--- /dev/null
@@ -0,0 +1,179 @@
+/***************************************************************************
+ * RCS INFORMATION:
+ *
+ *   $RCSfile$
+ *   $Author$       $Locker$        $State$
+ *   $Revision$     $Date$
+ *
+ ***************************************************************************
+ *
+ * $Log$
+ * Revision 1.1  1997-11-26 19:13:59  milind
+ * Origin2000 Posix Threads Version
+ *
+ * Revision 1.5  1997/08/06 20:35:58  jyelon
+ * Fixed bugs.
+ *
+ * Revision 1.4  1997/07/28 19:01:08  jyelon
+ * *** empty log message ***
+ *
+ * Revision 1.3  1997/07/26 16:42:03  jyelon
+ * *** empty log message ***
+ *
+ * Revision 1.2  1997/07/07 22:13:50  milind
+ * Made threads to work.
+ *
+ * Revision 1.1  1997/03/28 17:38:23  milind
+ * Added Origin2000 version.
+ *
+ * Revision 1.2  1997/03/25 23:09:09  milind
+ * Got threads to work on 64-bit irix. Had to add JB_TWEAKING_ORIGIN flag to
+ * all the conv-mach.h files. Also, _PAGESZ was undefined on irix. Added
+ * code to memory.c to make it a static variable.
+ *
+ * Revision 1.1  1997/03/19 21:45:27  milind
+ * net-irix-64 bit bersion. Not tested yet.
+ *
+ * Revision 1.3  1997/02/13 09:31:45  jyelon
+ * Updated for new main/ConverseInit structure.
+ *
+ * Revision 1.2  1997/02/08 14:10:19  jyelon
+ * Correcting bugs in network version.
+ *
+ * Revision 1.1  1997/01/28 16:26:42  milind
+ * Added net-irix version. Had to fix the charm++ translator for that.
+ * Also, threads are currently not supported on net-irix.
+ * Added a test program to measure scheduling overhead for both
+ * normal as well as threaded entry methods.
+ *
+ * Revision 2.28  1997/01/17 15:50:26  jyelon
+ * Minor adjustments to deal with recent changes to Common code.
+ *
+ * Revision 2.27  1996/11/23 02:25:39  milind
+ * Fixed several subtle bugs in the converse runtime for convex
+ * exemplar.
+ *
+ * Revision 2.26  1996/11/08 22:22:59  brunner
+ * Put _main in for HP-UX CC compilation.  It is ignored according to the
+ * CMK_USE_HP_MAIN_FIX flag.
+ *
+ * Revision 2.25  1996/10/24 19:40:26  milind
+ * Added CMK_IS_HETERO to all the net-all versions.
+ *
+ * Revision 2.24  1996/08/08 20:16:53  jyelon
+ * *** empty log message ***
+ *
+ * Revision 2.23  1996/07/16 17:23:37  jyelon
+ * Renamed a flag.
+ *
+ * Revision 2.22  1996/07/16 05:20:41  milind
+ * Added CMK_VECTOR_SEND
+ *
+ * Revision 2.21  1996/07/15  20:58:27  jyelon
+ * Flags now use #if, not #ifdef.  Also cleaned up a lot.
+ *
+ *
+ **************************************************************************/
+
+#ifndef _CONV_MACH_H
+#define _CONV_MACH_H
+
+#define CMK_ASYNC_NOT_NEEDED                               1
+#define CMK_ASYNC_USE_FIOASYNC_AND_FIOSETOWN               0
+#define CMK_ASYNC_USE_FIOASYNC_AND_SIOCSPGRP               0
+#define CMK_ASYNC_USE_FIOSSAIOSTAT_AND_FIOSSAIOOWN         0
+#define CMK_ASYNC_USE_F_SETFL_AND_F_SETOWN                 0
+
+#define CMK_CMIDELIVERS_USE_COMMON_CODE                    1
+#define CMK_CMIDELIVERS_USE_SPECIAL_CODE                   0
+
+#define CMK_CMIPRINTF_IS_A_BUILTIN                         0
+#define CMK_CMIPRINTF_IS_JUST_PRINTF                       1
+
+#define CMK_COMMHANDLE_IS_AN_INTEGER                       0
+#define CMK_COMMHANDLE_IS_A_POINTER                        1
+
+#define CMK_CSDEXITSCHEDULER_IS_A_FUNCTION                 0
+#define CMK_CSDEXITSCHEDULER_SET_CSDSTOPFLAG               1
+
+#define CMK_DEFAULT_MAIN_USES_COMMON_CODE                  1
+
+#define CMK_FIX_HP_CONNECT_BUG                             0
+
+#define CMK_GETPAGESIZE_AVAILABLE                          1
+
+#define CMK_IS_HETERO                                      0
+
+#define CMK_MACHINE_NAME                                   "origin-pthreads"
+
+#define CMK_MALLOC_USE_GNU_MALLOC                          0
+#define CMK_MALLOC_USE_OS_BUILTIN                          1
+
+#define CMK_MSG_HEADER_SIZE_BYTES                          4
+#define CMK_MSG_HEADER_BLANK_SPACE                         0
+
+#define CMK_PREPROCESSOR_CANNOT_DO_CONCATENATION           0
+#define CMK_PREPROCESSOR_USES_ANSI_STANDARD_CONCATENATION  1
+
+#define CMK_PROTOTYPES_FAIL                                0
+#define CMK_PROTOTYPES_WORK                                1
+
+#define CMK_RSH_IS_A_COMMAND                               0
+#define CMK_RSH_NOT_NEEDED                                 1
+#define CMK_RSH_USE_REMSH                                  0
+
+#define CMK_SHARED_VARS_EXEMPLAR                           0
+#define CMK_SHARED_VARS_UNAVAILABLE                        0
+#define CMK_SHARED_VARS_UNIPROCESSOR                       0
+#define CMK_SHARED_VARS_SUN_THREADS                        0
+#define CMK_SHARED_VARS_PTHREADS                           1
+
+#define CMK_SIGHOLD_IS_A_BUILTIN                           0
+#define CMK_SIGHOLD_NOT_NEEDED                             1
+#define CMK_SIGHOLD_USE_SIGMASK                            0
+
+#define CMK_SIGNAL_NOT_NEEDED                              1
+#define CMK_SIGNAL_USE_SIGACTION                           0
+#define CMK_SIGNAL_USE_SIGACTION_WITH_RESTART              0
+
+#define CMK_SIZE_T                                         unsigned long
+
+#define CMK_STATIC_PROTO_FAILS                             0
+#define CMK_STATIC_PROTO_WORKS                             1
+
+#define CMK_STRERROR_IS_A_BUILTIN                          1
+#define CMK_STRERROR_USE_SYS_ERRLIST                       0
+
+#define CMK_STRINGS_USE_OWN_DECLARATIONS                   0
+#define CMK_STRINGS_USE_STRINGS_H                          0
+#define CMK_STRINGS_USE_STRING_H                           1
+
+#define CMK_SYNCHRONIZE_ON_TCP_CLOSE                       0
+
+#define CMK_THREADS_REQUIRE_NO_CPV                         0
+
+#define CMK_THREADS_UNAVAILABLE                            0
+#define CMK_THREADS_USE_ALLOCA                             0
+#define CMK_THREADS_USE_JB_TWEAKING                        0
+#define CMK_THREADS_USE_JB_TWEAKING_EXEMPLAR               0
+#define CMK_THREADS_USE_JB_TWEAKING_ORIGIN                 1
+
+#define CMK_TIMER_USE_GETRUSAGE                            0
+#define CMK_TIMER_USE_SPECIAL                              0
+#define CMK_TIMER_USE_TIMES                                1
+
+#define CMK_VECTOR_SEND_USES_COMMON_CODE                   1
+#define CMK_VECTOR_SEND_USES_SPECIAL_CODE                  0
+
+#define CMK_WAIT_NOT_NEEDED                                0
+#define CMK_WAIT_USES_SYS_WAIT_H                           1
+#define CMK_WAIT_USES_WAITFLAGS_H                          0
+
+#define CMK_WHEN_PROCESSOR_IDLE_BUSYWAIT                   1
+#define CMK_WHEN_PROCESSOR_IDLE_USLEEP                     0
+
+#define CMK_USE_HP_MAIN_FIX                                0
+#define CMK_DONT_USE_HP_MAIN_FIX                           1
+
+#endif
+
diff --git a/src/arch/origin-pthreads/machine.c b/src/arch/origin-pthreads/machine.c
new file mode 100644 (file)
index 0000000..8c088a8
--- /dev/null
@@ -0,0 +1,484 @@
+#include <errno.h>
+#include <pthread.h>
+#include <sched.h>
+
+#define _POSIX1C
+#define _NO_ANSIMODE
+
+#include <stdio.h>
+#include <sys/types.h>
+#include <limits.h>
+#include <unistd.h>
+
+#include "converse.h"
+
+extern void *FIFO_Create(void);
+extern void FIFO_EnQueue(void *, void *);
+
+#define BLK_LEN  512
+
+typedef struct {
+  pthread_mutex_t mutex;
+  void     **blk;
+  unsigned int blk_len;
+  unsigned int first;
+  unsigned int len;
+  unsigned int maxlen;
+} McQueue;
+
+static McQueue *McQueueCreate(void);
+static void McQueueAddToBack(McQueue *queue, void *element);
+static void *McQueueRemoveFromFront(McQueue *queue);
+static McQueue **MsgQueue;
+
+CpvDeclare(void*, CmiLocalQueue);
+
+int Cmi_argc;
+int Cmi_numpes;
+int Cmi_usched;
+int Cmi_initret;
+CmiStartFn Cmi_startFn;
+
+pthread_key_t perThreadKey;
+
+static void *threadInit(void *arg);
+
+pthread_mutex_t memory_mutex;
+
+void CmiMemLock() {pthread_mutex_lock(&memory_mutex);}
+void CmiMemUnlock() {pthread_mutex_unlock(&memory_mutex);}
+
+int barrier;
+pthread_cond_t barrier_cond;
+pthread_mutex_t barrier_mutex;
+
+void CmiNodeBarrier(void)
+{
+  pthread_mutex_lock(&barrier_mutex);
+  barrier++;
+  if(barrier!=CmiNumPes())
+    pthread_cond_wait(&barrier_cond, &barrier_mutex);
+  else {
+    barrier = 0;
+    pthread_cond_broadcast(&barrier_cond);
+  }
+  pthread_mutex_unlock(&barrier_mutex);
+}
+
+CmiNodeLock CmiCreateLock(void)
+{
+  pthread_mutex_t *lock;
+  lock = (pthread_mutex_t *) CmiAlloc(sizeof(pthread_mutex_t));
+  pthread_mutex_init(lock, (pthread_mutexattr_t *) 0);
+  return lock;
+}
+
+void CmiLock(CmiNodeLock lock)
+{
+  pthread_mutex_lock(lock);
+}
+
+void CmiUnlock(CmiNodeLock lock)
+{
+  pthread_mutex_unlock(lock);
+}
+
+int CmiTryLock(CmiNodeLock lock)
+{
+  return pthread_mutex_trylock(lock);
+}
+
+void CmiDestroyLock(CmiNodeLock lock)
+{
+  pthread_mutex_destroy(lock);
+}
+
+int CmiMyPe()
+{
+  int mype = (int) pthread_getspecific(perThreadKey);
+  return mype;
+}
+
+void *CmiAlloc(int size)
+{
+  char *res;
+  res =(char *) malloc(size+8);
+  if (res==(char *)0) { 
+    CmiError("%d:Memory allocation failed.",CmiMyPe()); 
+    abort();
+  }
+  ((int *)res)[0]=size;
+  return (void *)(res+8);
+}
+
+int CmiSize(void *blk)
+{
+  return ((int *)( ((char *) blk) - 8))[0];
+}
+
+void CmiFree(void *blk)
+{
+  free( ((char *)blk) - 8);
+}
+
+
+int CmiAsyncMsgSent(CmiCommHandle msgid)
+{
+  return 0;
+}
+
+
+typedef struct {
+  char       **argv;
+  int        mype;
+} USER_PARAMETERS;
+
+void ConverseInit(int argc, char **argv, CmiStartFn fn, int usched, int initret)
+{
+  int i;
+  USER_PARAMETERS *usrparam;
+  pthread_t *aThread;
+  Cmi_numpes = 0; 
+  Cmi_usched = usched;
+  Cmi_initret = initret;
+  Cmi_startFn = fn;
+  Cmi_argc = argc;
+
+  for(i=0;i<Cmi_argc;i++) {
+    if (strcmp(argv[i], "+p") == 0) {
+      sscanf(argv[i+1], "%d", &Cmi_numpes);
+      break;
+    } else {
+      if (sscanf(argv[i], "+p%d", &Cmi_numpes) == 1) 
+       break;
+    }
+  }
+
+  if (Cmi_numpes <= 0)
+  {
+    CmiError("Error: requested number of processors is invalid %d\n",
+              Cmi_numpes);
+    abort();
+  }
+
+
+  pthread_mutex_init(&memory_mutex, (pthread_mutexattr_t *) 0);
+
+  MsgQueue=(McQueue **)CmiAlloc(Cmi_numpes*sizeof(McQueue *));
+  if (MsgQueue == (McQueue **)0) {
+    CmiError("Cannot Allocate Memory...\n");
+    abort();
+  }
+  for(i=0; i<Cmi_numpes; i++) 
+    MsgQueue[i] = McQueueCreate();
+
+  pthread_key_create(&perThreadKey, (void *) 0);
+  barrier = 0;
+  pthread_cond_init(&barrier_cond, (pthread_condattr_t *) 0);
+  pthread_mutex_init(&barrier_mutex, (pthread_mutexattr_t *) 0);
+
+  aThread = (pthread_t *) CmiAlloc(sizeof(pthread_t) * Cmi_numpes);
+  for(i=0; i<Cmi_numpes; i++) {
+    int j;
+    char **uargv = (char **) CmiAlloc(sizeof(char *) * (Cmi_argc+1));
+
+    for (j=0;j<Cmi_argc;j++)
+      uargv[j] = argv[j];
+    uargv[j] = 0;
+
+    usrparam = (USER_PARAMETERS *) CmiAlloc(sizeof(USER_PARAMETERS));
+    usrparam->argv = uargv;
+    usrparam->mype = i;
+
+    pthread_create(&aThread[i],(pthread_attr_t *)0,threadInit,(void *)usrparam);
+  }
+  for(i=0;i<Cmi_numpes;i++) {
+    void *retVal;
+    pthread_join(aThread[i], &retVal);
+  }
+}
+
+static void neighbour_init(int);
+
+static void *threadInit(void *arg)
+{
+  USER_PARAMETERS *usrparam;
+  usrparam = (USER_PARAMETERS *) arg;
+
+
+  pthread_setspecific(perThreadKey, (void *) usrparam->mype);
+
+  ConverseCommonInit(usrparam->argv);
+  CthInit(usrparam->argv);
+  neighbour_init(CmiMyPe());
+  CpvInitialize(void*, CmiLocalQueue);
+  CpvAccess(CmiLocalQueue) = (void *) FIFO_Create();
+  CmiSpanTreeInit();
+  CmiTimerInit();
+  if (Cmi_initret==0) {
+    Cmi_startFn(Cmi_argc, usrparam->argv);
+    if (Cmi_usched==0) CsdScheduler(-1);
+    ConverseExit();
+  }
+}
+
+
+void ConverseExit(void)
+{
+  ConverseCommonExit();
+}
+
+
+void CmiDeclareArgs(void)
+{
+}
+
+
+void CmiNotifyIdle()
+{
+}
+
+void *CmiGetNonLocal()
+{
+  return McQueueRemoveFromFront(MsgQueue[CmiMyPe()]);
+}
+
+
+void CmiSyncSendFn(int destPE, int size, char *msg)
+{
+  char *buf;
+
+  buf=(void *)CmiAlloc(size);
+  memcpy(buf,msg,size);
+  McQueueAddToBack(MsgQueue[destPE],buf); 
+}
+
+
+CmiCommHandle CmiAsyncSendFn(int destPE, int size, char *msg)
+{
+  CmiSyncSendFn(destPE, size, msg); 
+  return 0;
+}
+
+
+void CmiFreeSendFn(int destPE, int size, char *msg)
+{
+  if (CmiMyPe()==destPE) {
+    FIFO_EnQueue(CpvAccess(CmiLocalQueue),msg);
+  } else {
+    McQueueAddToBack(MsgQueue[destPE],msg); 
+  }
+}
+
+void CmiSyncBroadcastFn(int size, char *msg)
+{
+  int i;
+  for(i=0; i<Cmi_numpes; i++)
+    if (CmiMyPe() != i) CmiSyncSendFn(i,size,msg);
+}
+
+CmiCommHandle CmiAsyncBroadcastFn(int size, char *msg)
+{
+  CmiSyncBroadcastFn(size, msg);
+  return 0;
+}
+
+void CmiFreeBroadcastFn(int size, char *msg)
+{
+  CmiSyncBroadcastFn(size,msg);
+  CmiFree(msg);
+}
+
+void CmiSyncBroadcastAllFn(int size, char *msg)
+{
+  int i;
+  for(i=0; i<CmiNumPes(); i++) 
+    CmiSyncSendFn(i,size,msg);
+}
+
+
+CmiCommHandle CmiAsyncBroadcastAllFn(int size, char *msg)
+{
+  CmiSyncBroadcastAllFn(size, msg);
+  return 0; 
+}
+
+
+void CmiFreeBroadcastAllFn(int size, char *msg)
+{
+  int i;
+  for(i=0; i<CmiNumPes(); i++) {
+    if(CmiMyPe() != i) {
+      CmiSyncSendFn(i,size,msg);
+    }
+  }
+  FIFO_EnQueue(CpvAccess(CmiLocalQueue),msg);
+}
+
+/* ********************************************************************** */
+/* The following functions are required by the load balance modules       */
+/* ********************************************************************** */
+
+static int _MC_neighbour[4]; 
+static int _MC_numofneighbour;
+
+long CmiNumNeighbours(int node)
+{
+  if (node == CmiMyPe() ) 
+   return  _MC_numofneighbour;
+  else 
+   return 0;
+}
+
+
+void CmiGetNodeNeighbours(int node, int *neighbours)
+{
+  int i;
+
+  if (node == CmiMyPe() )
+    for(i=0; i<_MC_numofneighbour; i++) 
+      neighbours[i] = _MC_neighbour[i];
+}
+
+
+int CmiNeighboursIndex(int node, int neighbour)
+{
+  int i;
+
+  for(i=0; i<_MC_numofneighbour; i++)
+    if (_MC_neighbour[i] == neighbour) return i;
+  return(-1);
+}
+
+
+static void neighbour_init(int p)
+{
+  int a,b,n;
+
+  n = CmiNumPes();
+  a = (int)sqrt((double)n);
+  b = (int) ceil( ((double)n / (double)a) );
+
+   
+  _MC_numofneighbour = 0;
+   
+  /* east neighbour */
+  if( (p+1)%b == 0 )
+    n = p-b+1;
+  else {
+    n = p+1;
+    if(n>=CmiNumPes()) 
+      n = (a-1)*b; /* west-south corner */
+  }
+  if(neighbour_check(p,n) ) 
+    _MC_neighbour[_MC_numofneighbour++] = n;
+
+  /* west neigbour */
+  if( (p%b) == 0) {
+    n = p+b-1;
+  if(n >= CmiNumPes()) 
+    n = CmiNumPes()-1;
+  } else
+    n = p-1;
+  if(neighbour_check(p,n) ) 
+    _MC_neighbour[_MC_numofneighbour++] = n;
+
+  /* north neighbour */
+  if( (p/b) == 0) {
+    n = (a-1)*b+p;
+    if(n >= CmiNumPes()) 
+      n = n-b;
+  } else
+    n = p-b;
+  if(neighbour_check(p,n) ) 
+    _MC_neighbour[_MC_numofneighbour++] = n;
+    
+  /* south neighbour */
+  if( (p/b) == (a-1) )
+    n = p%b;
+  else {
+    n = p+b;
+    if(n >= CmiNumPes()) 
+      n = n%b;
+  } 
+  if(neighbour_check(p,n) ) 
+    _MC_neighbour[_MC_numofneighbour++] = n;
+}
+
+static neighbour_check(int p, int n)
+{
+    int i; 
+    if(n==p) 
+      return 0;
+    for(i=0; i<_MC_numofneighbour; i++) 
+      if (_MC_neighbour[i] == n) return 0;
+    return 1; 
+}
+
+/* ****************************************************************** */
+/*    The following internal functions implements FIFO queues for     */
+/*    messages. These queues are shared among threads                 */
+/* ****************************************************************** */
+
+static void ** AllocBlock(unsigned int len)
+{
+  void **blk;
+
+  blk=(void **)CmiAlloc(len*sizeof(void *));
+  return blk;
+}
+
+static void 
+SpillBlock(void **srcblk, void **destblk, unsigned int first, unsigned int len)
+{
+  memcpy(destblk, &(srcblk[first]), (len-first)*sizeof(void *));
+  memcpy(&(destblk[len-first]),srcblk,first*sizeof(void *));
+}
+
+McQueue * McQueueCreate(void)
+{
+  McQueue *queue;
+
+  queue = (McQueue *) CmiAlloc(sizeof(McQueue));
+  pthread_mutex_init(&(queue->mutex), (pthread_mutexattr_t *) 0);
+  queue->blk = AllocBlock(BLK_LEN);
+  queue->blk_len = BLK_LEN;
+  queue->first = 0;
+  queue->len = 0;
+  queue->maxlen = 0;
+  return queue;
+}
+
+void McQueueAddToBack(McQueue *queue, void *element)
+{
+  pthread_mutex_lock(&(queue->mutex));
+  if(queue->len==queue->blk_len) {
+    void **blk;
+
+    queue->blk_len *= 3;
+    blk = AllocBlock(queue->blk_len);
+    SpillBlock(queue->blk, blk, queue->first, queue->len);
+    CmiFree(queue->blk);
+    queue->blk = blk;
+    queue->first = 0;
+  }
+  queue->blk[(queue->first+queue->len++)%queue->blk_len] = element;
+  if(queue->len>queue->maxlen)
+    queue->maxlen = queue->len;
+  pthread_mutex_unlock(&(queue->mutex));
+}
+
+
+void * McQueueRemoveFromFront(McQueue *queue)
+{
+  void *element = 0;
+  pthread_mutex_lock(&(queue->mutex));
+  if(queue->len) {
+    element = queue->blk[queue->first++];
+    queue->first = (queue->first+queue->blk_len)%queue->blk_len;
+    queue->len--;
+  }
+  pthread_mutex_unlock(&(queue->mutex));
+  return element;
+}
diff --git a/src/arch/origin-pthreads/spantree.c b/src/arch/origin-pthreads/spantree.c
new file mode 100644 (file)
index 0000000..e50d326
--- /dev/null
@@ -0,0 +1,105 @@
+/***************************************************************************
+ * RCS INFORMATION:
+ *
+ *     $RCSfile$
+ *     $Author$        $Locker$                $State$
+ *     $Revision$      $Date$
+ *
+ ***************************************************************************
+ * DESCRIPTION:
+ *
+ ***************************************************************************
+ * REVISION HISTORY:
+ *
+ * $Log$
+ * Revision 1.1  1997-11-26 19:14:00  milind
+ * Origin2000 Posix Threads Version
+ *
+ * Revision 1.2  1997/10/29 23:53:14  milind
+ * Fixed CthInitialize bug on uth machines.
+ *
+ * Revision 1.1  1997/03/28 17:38:25  milind
+ * Added Origin2000 version.
+ *
+ * Revision 2.6  1995/10/27 21:45:35  jyelon
+ * Changed CmiNumPe --> CmiNumPes
+ *
+ * Revision 2.5  1995/10/25  19:56:05  jyelon
+ * Changed CmiSyncSendFn --> CmiSyncSend
+ *
+ * Revision 2.4  1995/10/19  18:18:24  jyelon
+ * added "converse.h"
+ *
+ * Revision 2.3  1995/09/29  09:50:07  jyelon
+ * CmiGet-->CmiDeliver, added protos, etc.
+ *
+ * Revision 2.2  1995/09/20  15:12:09  sanjeev
+ * CmiSpanTreeChild -> CmiSpanTreeChildren
+ *
+ * Revision 2.1  1995/06/09  21:22:00  gursoy
+ * Cpv macros moved to converse
+ *
+ * Revision 2.0  1995/06/08  16:35:12  gursoy
+ * Reorganized directory structure
+ *
+ ***************************************************************************/
+static char ident[] = "@(#)$Header$";
+
+/* This file contains all the spanning tree functions */
+#include <converse.h>
+
+
+#define MAXSPAN    4          /* The maximum permitted span on 
+                                each node of the spanning tree */
+
+void CmiSpanTreeInit(void)
+{
+}
+
+
+int CmiSpanTreeParent(node)
+int node;
+{
+    if (node == 0)
+         return -1;
+    else return ((node - 1) / MAXSPAN);   /* integer division */
+}
+
+int CmiSpanTreeRoot()
+{
+    return 0;
+}
+
+void CmiSpanTreeChildren(node, children)
+int node, *children;
+{
+    int i;
+
+    for (i = 1; i <= MAXSPAN ; i++)
+       if (MAXSPAN * node + i < CmiNumPes())
+            children[i-1] = node * MAXSPAN + i;
+       else children[i-1] = -1;
+}
+
+
+int CmiNumSpanTreeChildren(node)
+int node;
+{
+    if ((node + 1) * MAXSPAN < CmiNumPes())
+         return MAXSPAN;
+    else if (node * MAXSPAN + 1 >= CmiNumPes())
+        return 0;
+    else return ((CmiNumPes() - 1) - node * MAXSPAN);
+}
+
+void CmiSendToSpanTreeLeaves(size, msg)
+int size;
+char * msg;
+{
+    int node;
+
+    for (node = (CmiNumPes() - 2) / MAXSPAN;   /* integer division */
+        node < CmiNumPes(); node++)
+        CmiSyncSend(node, size, msg);
+}
+