Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Merge branch 'master' of git+ssh://scm.gforge.inria.fr//gitroot/simgrid/simgrid
authorJonathan Rouzaud-Cornabas <jonathan.rouzaud-cornabas@ens-lyon.fr>
Mon, 25 Mar 2013 16:35:26 +0000 (17:35 +0100)
committerJonathan Rouzaud-Cornabas <jonathan.rouzaud-cornabas@ens-lyon.fr>
Mon, 25 Mar 2013 16:35:26 +0000 (17:35 +0100)
35 files changed:
buildtools/Cmake/DefinePackages.cmake
buildtools/Cmake/MakeLib.cmake
examples/msg/mc/bugged1.tesh
examples/msg/mc/bugged1_liveness.tesh
examples/msg/mc/chord/chord_neverjoin.tesh
src/bindings/java/jmsg_task.h
src/include/smpi/smpi_interface.h
src/mc/mc_dpor.c
src/mc/mc_global.c
src/mc/mc_liveness.c
src/mc/mc_pair.c
src/mc/mc_private.h
src/simgrid/sg_config.c
src/smpi/colls/COPYRIGHTS [new file with mode: 0644]
src/smpi/colls/alltoall-2dmesh.c [new file with mode: 0644]
src/smpi/colls/alltoall-3dmesh.c [new file with mode: 0644]
src/smpi/colls/alltoall-bruck.c [new file with mode: 0644]
src/smpi/colls/alltoall-native.c [new file with mode: 0644]
src/smpi/colls/alltoall-pair-light-barrier.c [new file with mode: 0644]
src/smpi/colls/alltoall-pair-mpi-barrier.c [new file with mode: 0644]
src/smpi/colls/alltoall-pair-one-barrier.c [new file with mode: 0644]
src/smpi/colls/alltoall-pair.c [new file with mode: 0644]
src/smpi/colls/alltoall-rdb.c [new file with mode: 0644]
src/smpi/colls/alltoall-ring-light-barrier.c [new file with mode: 0644]
src/smpi/colls/alltoall-ring-mpi-barrier.c [new file with mode: 0644]
src/smpi/colls/alltoall-ring-one-barrier.c [new file with mode: 0644]
src/smpi/colls/alltoall-ring.c [new file with mode: 0644]
src/smpi/colls/alltoall-simple.c [new file with mode: 0644]
src/smpi/colls/colls.h [new file with mode: 0644]
src/smpi/private.h
src/smpi/smpi_coll.c
src/smpi/smpi_mpi.c
src/smpi/smpi_pmpi.c
src/xbt/automaton/parserPromela.tab.cacc
src/xbt/mmalloc/mm_diff.c

index 2ff4816..0cf83fa 100644 (file)
@@ -35,6 +35,7 @@ set(EXTRA_DIST
   src/simix/smx_smurf_private.h
   src/simix/smx_synchro_private.h
   src/smpi/README
+  src/smpi/colls/colls.h
   src/smpi/private.h
   src/smpi/smpi_mpi_dt_private.h
   src/surf/cpu_ti_private.h
@@ -107,6 +108,19 @@ set(SMPI_SRC
   src/smpi/smpi_mpi_dt.c
   src/smpi/smpi_pmpi.c
   src/smpi/smpi_replay.c
+  src/smpi/colls/alltoall-2dmesh.c
+  src/smpi/colls/alltoall-3dmesh.c
+  #  src/smpi/colls/alltoall-bruck.c
+  src/smpi/colls/alltoall-pair.c
+  src/smpi/colls/alltoall-pair-light-barrier.c
+  src/smpi/colls/alltoall-pair-mpi-barrier.c
+  src/smpi/colls/alltoall-pair-one-barrier.c
+  src/smpi/colls/alltoall-rdb.c
+  src/smpi/colls/alltoall-ring.c
+  src/smpi/colls/alltoall-ring-light-barrier.c
+  src/smpi/colls/alltoall-ring-mpi-barrier.c
+  src/smpi/colls/alltoall-ring-one-barrier.c
+  src/smpi/colls/alltoall-simple.c
   )
 
 if(SMPI_F2C)
@@ -539,6 +553,7 @@ set(simgrid_sources
   ${SURF_SRC}
   ${TRACING_SRC}
   ${XBT_SRC}
+  ${SMPI_SRC}
   )
 
 if(${HAVE_JEDULE})
index f7adde3..e31007b 100644 (file)
@@ -98,6 +98,7 @@ if(HAVE_MC)
   # The availability of libunwind was checked in CompleteInFiles.cmake
   #   (that includes FindLibunwind.cmake), so simply load it now.
   
+  SET(SIMGRID_DEP "${SIMGRID_DEP} -lunwind")
   # This supposes that the host machine is either an AMD or a X86.
   # This is deeply wrong, and should be fixed by manually loading -lunwind-PLAT (FIXME)
   if(PROCESSOR_x86_64)
index 6b0b70f..6a11193 100644 (file)
@@ -42,4 +42,3 @@ $ ${bindir:=.}/bugged1 --cfg=model-check:1 "--log=root.fmt:[%10.6r]%e(%i:%P@%h)%
 > [  0.000000] (1:server@HostA) Expanded states = 36
 > [  0.000000] (1:server@HostA) Visited states = 75
 > [  0.000000] (1:server@HostA) Executed transitions = 70
-> [  0.000000] (1:server@HostA) Expanded / Visited = 2.083333
index b083c7c..b0f05b3 100644 (file)
@@ -39,7 +39,6 @@ $ ${bindir:=.}/bugged1_liveness --cfg=model-check:1 --cfg=contexts/factory:ucont
 > [0.000000] [mc_global/INFO] [(3)client] iSend (src=client, buff=(verbose only), size=(verbose only))
 > [0.000000] [mc_global/INFO] [(1)coordinator] Wait (comm=(verbose only) [(3)client -> (1)coordinator])
 > [0.000000] [mc_global/INFO] [(1)coordinator] iSend (src=coordinator, buff=(verbose only), size=(verbose only))
-> [0.000000] [mc_global/INFO] Expanded states = 22
-> [0.000000] [mc_global/INFO] Visited states = 21
+> [0.000000] [mc_global/INFO] Expanded pairs = 23
+> [0.000000] [mc_global/INFO] Visited pairs = 21
 > [0.000000] [mc_global/INFO] Executed transitions = 21
-> [0.000000] [mc_global/INFO] Expanded / Visited = 0.954545
index 2688128..b458c9c 100644 (file)
@@ -25,7 +25,6 @@ $ ${bindir:=.}/chord_liveness --cfg=model-check:1 --cfg=contexts/factory:ucontex
 > [0.000000] [mc_global/INFO] [(1)node] Wait (comm=(verbose only) [(3)node -> (1)node])
 > [0.000000] [mc_global/INFO] [(1)node] iRecv (dst=node, buff=(verbose only), size=(verbose only))
 > [0.000000] [mc_global/INFO] [(1)node] Test FALSE (comm=(verbose only))
-> [0.000000] [mc_global/INFO] Expanded states = 11
-> [0.000000] [mc_global/INFO] Visited states = 10
+> [0.000000] [mc_global/INFO] Expanded pairs = 14
+> [0.000000] [mc_global/INFO] Visited pairs = 10
 > [0.000000] [mc_global/INFO] Executed transitions = 10
-> [0.000000] [mc_global/INFO] Expanded / Visited = 0.909091
index b014776..8078984 100644 (file)
@@ -225,6 +225,21 @@ JNIEXPORT jobject JNICALL
  */
 JNIEXPORT jobject JNICALL
 Java_org_simgrid_msg_Task_irecv(JNIEnv * env, jclass cls, jstring jmailbox);
+/**
+ * Class               org_simgrid_msg_Task
+ * Method              receiveBounded
+ */
+JNIEXPORT jobject JNICALL
+Java_org_simgrid_msg_Task_receiveBounded(JNIEnv * env, jclass cls,
+                                         jstring jalias, jdouble jtimeout,
+                                         jobject jhost, jdouble rate);
+/**
+ * Class               org_simgrid_msg_Task
+ * Method              irecvBounded
+ */
+JNIEXPORT jobject JNICALL
+Java_org_simgrid_msg_Task_irecvBounded(JNIEnv * env, jclass cls,
+                                       jstring jmailbox, jdouble rate);
 /**
  * Class               org_simgrid_msg_Task
  * Method              isend
@@ -234,8 +249,7 @@ JNIEXPORT jobject JNICALL
 Java_org_simgrid_msg_Task_isend(JNIEnv *env, jobject jtask, jstring jmailbox);
 /**
  * Class               org_simgrid_msg_Task
- * Method              isend
- * Signature   (Lorg/simgrid/msg/Task;Ljava/lang/String;)Lorg/simgrid/msg/Comm;
+ * Method              isendBounded
  */
 JNIEXPORT jobject JNICALL
 Java_org_simgrid_msg_Task_isendBounded(JNIEnv *env, jobject jtask, jstring jmailbox, jdouble maxrate);
index c975477..ed7f5c4 100644 (file)
@@ -1,3 +1,7 @@
+#ifndef _SMPI_INTERFACE_H
+#define _SMPI_INTERFACE_H
+#include "smpi/smpi.h"
+
 /********** Tracing **********/
 /* from smpi_instr.c */
 void TRACE_smpi_alloc(void);
@@ -8,3 +12,30 @@ void TRACE_smpi_send(int rank, int src, int dst);
 void TRACE_smpi_recv(int rank, int src, int dst);
 void TRACE_smpi_init(int rank);
 void TRACE_smpi_finalize(int rank);
+
+/** \brief MPI collective description
+ */
+
+typedef struct mpi_coll_description {
+  const char *name;
+  const char *description;
+  void* coll;
+} s_mpi_coll_description_t, *mpi_coll_description_t;
+
+/** \ingroup MPI alltoallcollectives
+ *  \brief The list of all available alltoall collectives
+ */
+XBT_PUBLIC_DATA(s_mpi_coll_description_t) mpi_coll_alltoall_description[];
+int (*mpi_coll_alltoall_fun)(void *, int, MPI_Datatype, void*, int, MPI_Datatype, MPI_Comm);
+
+/** \ingroup MPI allgather
+ *  \brief The list of all available allgather collectives
+ */
+XBT_PUBLIC_DATA(s_mpi_coll_description_t) mpi_coll_allgather_description[];
+int (*mpi_coll_allgather_fun)(void *, int, MPI_Datatype, void*, int, MPI_Datatype, MPI_Comm);
+
+XBT_PUBLIC(void) coll_help(const char *category, s_mpi_coll_description_t * table);
+XBT_PUBLIC(int) find_coll_description(s_mpi_coll_description_t * table,
+                           const char *name);
+
+#endif                          /* _SMPI_INTERFAC_H */
index de9b988..a97440a 100644 (file)
@@ -9,10 +9,7 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(mc_dpor, mc,
                                 "Logging specific to MC DPOR exploration");
 
 xbt_dynar_t visited_states;
-
-static int is_visited_state(void);
-static void visited_state_free(mc_visited_state_t state);
-static void visited_state_free_voidp(void *s);
+xbt_dict_t first_enabled_state;
 
 static void visited_state_free(mc_visited_state_t state){
   if(state){
@@ -196,6 +193,8 @@ void MC_dpor_init()
   initial_state = MC_state_new();
   visited_states = xbt_dynar_new(sizeof(mc_visited_state_t), visited_state_free_voidp);
 
+  first_enabled_state = xbt_dict_new_homogeneous(&xbt_free_f);
+
   MC_UNSET_RAW_MEM;
 
   XBT_DEBUG("**************************************************");
@@ -210,12 +209,26 @@ void MC_dpor_init()
   xbt_swag_foreach(process, simix_global->process_list){
     if(MC_process_is_enabled(process)){
       MC_state_interleave_process(initial_state, process);
-      XBT_DEBUG("Process %lu enabled with simcall %d", process->pid, process->simcall.call);
+      if(mc_reduce_kind != e_mc_reduce_none)
+        break;
     }
   }
 
   xbt_fifo_unshift(mc_stack_safety, initial_state);
 
+  /* To ensure the soundness of DPOR, we have to keep a list of 
+     processes which are still enabled at each step of the exploration. 
+     If max depth is reached, we interleave them in the state in which they have 
+     been enabled for the first time. */
+  xbt_swag_foreach(process, simix_global->process_list){
+    if(MC_process_is_enabled(process)){
+      char *key = bprintf("%lu", process->pid);
+      char *data = bprintf("%d", xbt_fifo_size(mc_stack_safety));
+      xbt_dict_set(first_enabled_state, key, data, NULL);
+      xbt_free(key);
+    }
+  }
+
   MC_UNSET_RAW_MEM;
 
   if(raw_mem_set)
@@ -240,8 +253,7 @@ void MC_dpor(void)
   mc_state_t state = NULL, prev_state = NULL, next_state = NULL, restore_state=NULL;
   smx_process_t process = NULL;
   xbt_fifo_item_t item = NULL;
-  int pos, i, interleave_size;
-  int interleave_proc[simix_process_maxpid];
+  int pos;
   int visited_state;
 
   while (xbt_fifo_size(mc_stack_safety) > 0) {
@@ -260,7 +272,7 @@ void MC_dpor(void)
 
     /* If there are processes to interleave and the maximum depth has not been reached
        then perform one step of the exploration algorithm */
-    if (xbt_fifo_size(mc_stack_safety) < _sg_mc_max_depth &&
+    if (xbt_fifo_size(mc_stack_safety) <= _sg_mc_max_depth &&
         (req = MC_state_get_request(state, &value))) {
 
       /* Debug information */
@@ -275,35 +287,11 @@ void MC_dpor(void)
       MC_state_set_executed_request(state, req, value);
       mc_stats->executed_transitions++;
 
-      if(MC_state_interleave_size(state)){
-        MC_SET_RAW_MEM;
-        req2 = MC_state_get_internal_request(state);
-        req3 = *req2;
-        for(i=0; i<simix_process_maxpid; i++)
-          interleave_proc[i] = 0;
-        i=0;
-        interleave_size = MC_state_interleave_size(state);
-        while(i < interleave_size){
-          i++;
-          prev_req = MC_state_get_request(state, &value2);
-          if(prev_req != NULL){
-            MC_state_set_executed_request(state, prev_req, value2);
-            prev_req = MC_state_get_internal_request(state);
-            if(MC_request_depend(&req3, prev_req)){
-              XBT_DEBUG("Simcall %d in process %lu dependant with simcall %d in process %lu", req3.call, req3.issuer->pid, prev_req->call, prev_req->issuer->pid);  
-              interleave_proc[prev_req->issuer->pid] = 1;
-            }else{
-              XBT_DEBUG("Simcall %d in process %lu independant with simcall %d in process %lu", req3.call, req3.issuer->pid, prev_req->call, prev_req->issuer->pid); 
-              MC_state_remove_interleave_process(state, prev_req->issuer);
-            }
-          }
-        }
-        xbt_swag_foreach(process, simix_global->process_list){
-          if(interleave_proc[process->pid] == 1)
-            MC_state_interleave_process(state, process);
-        }
-        MC_UNSET_RAW_MEM;
-      }
+      MC_SET_RAW_MEM;
+      char *key = bprintf("%lu", req->issuer->pid);
+      xbt_dict_remove(first_enabled_state, key); 
+      xbt_free(key);
+      MC_UNSET_RAW_MEM;
 
       MC_state_set_executed_request(state, req, value);
 
@@ -324,7 +312,8 @@ void MC_dpor(void)
         xbt_swag_foreach(process, simix_global->process_list){
           if(MC_process_is_enabled(process)){
             MC_state_interleave_process(next_state, process);
-            XBT_DEBUG("Process %lu enabled with simcall %d", process->pid, process->simcall.call);
+            if(mc_reduce_kind != e_mc_reduce_none)
+              break;
           }
         }
 
@@ -343,6 +332,19 @@ void MC_dpor(void)
       }
 
       xbt_fifo_unshift(mc_stack_safety, next_state);
+
+      /* Insert in dict all enabled processes, if not included yet */
+      xbt_swag_foreach(process, simix_global->process_list){
+        if(MC_process_is_enabled(process)){
+          char *key = bprintf("%lu", process->pid);
+          if(xbt_dict_get_or_null(first_enabled_state, key) == NULL){
+            char *data = bprintf("%d", xbt_fifo_size(mc_stack_safety));
+            xbt_dict_set(first_enabled_state, key, data, NULL); 
+          }
+          xbt_free(key);
+        }
+      }
+
       MC_UNSET_RAW_MEM;
 
       xbt_free(req_str);
@@ -378,36 +380,64 @@ void MC_dpor(void)
          state that executed that previous request. */
       
       while ((state = xbt_fifo_shift(mc_stack_safety)) != NULL) {
-        req = MC_state_get_internal_request(state);
-        xbt_fifo_foreach(mc_stack_safety, item, prev_state, mc_state_t) {
-          if(MC_request_depend(req, MC_state_get_internal_request(prev_state))){
-            if(XBT_LOG_ISENABLED(mc_dpor, xbt_log_priority_debug)){
-              XBT_DEBUG("Dependent Transitions:");
-              prev_req = MC_state_get_executed_request(prev_state, &value);
-              req_str = MC_request_to_string(prev_req, value);
-              XBT_DEBUG("%s (state=%p)", req_str, prev_state);
-              xbt_free(req_str);
-              prev_req = MC_state_get_executed_request(state, &value);
-              req_str = MC_request_to_string(prev_req, value);
-              XBT_DEBUG("%s (state=%p)", req_str, state);
-              xbt_free(req_str);              
+        if(mc_reduce_kind != e_mc_reduce_none){
+          req = MC_state_get_internal_request(state);
+          /* If max_depth reached, check only for the last state if the request that has generated
+             it, depends on any other processes still enabled when max_depth reached */
+          if(xbt_fifo_size(mc_stack_safety) == _sg_mc_max_depth - 1){
+            req3 = *req;
+            xbt_swag_foreach(process, simix_global->process_list){
+              if(MC_process_is_enabled(process) && !MC_state_process_is_done(state, process)){
+                MC_state_interleave_process(state, process);
+                req2 = MC_state_get_request(state, &value2);
+                MC_state_set_executed_request(state, req2, value2);
+                req2 = MC_state_get_internal_request(state);
+                if(MC_request_depend(&req3, req2)){
+                  if(XBT_LOG_ISENABLED(mc_dpor, xbt_log_priority_debug)){
+                    XBT_DEBUG("Dependent Transitions:");
+                    req_str = MC_request_to_string(&req3, value);
+                    XBT_DEBUG("%s (state=%p)", req_str, state);
+                    xbt_free(req_str);
+                    req_str = MC_request_to_string(req2, value);
+                    XBT_DEBUG("%s (state=%p)", req_str, state);
+                    xbt_free(req_str);              
+                  } 
+                  MC_state_interleave_process(state, process);
+                  break;
+                }
+              }
             }
+          }
+          xbt_fifo_foreach(mc_stack_safety, item, prev_state, mc_state_t) {
+            if(MC_request_depend(req, MC_state_get_internal_request(prev_state))){
+              if(XBT_LOG_ISENABLED(mc_dpor, xbt_log_priority_debug)){
+                XBT_DEBUG("Dependent Transitions:");
+                prev_req = MC_state_get_executed_request(prev_state, &value);
+                req_str = MC_request_to_string(prev_req, value);
+                XBT_DEBUG("%s (state=%p)", req_str, prev_state);
+                xbt_free(req_str);
+                prev_req = MC_state_get_executed_request(state, &value);
+                req_str = MC_request_to_string(prev_req, value);
+                XBT_DEBUG("%s (state=%p)", req_str, state);
+                xbt_free(req_str);              
+              }
 
-            break;
-
-          }else if(req->issuer == MC_state_get_internal_request(prev_state)->issuer){
+              if(!MC_state_process_is_done(prev_state, req->issuer))
+                MC_state_interleave_process(prev_state, req->issuer);
+              else
+                XBT_DEBUG("Process %p is in done set", req->issuer);
 
-            XBT_DEBUG("Simcall %d and %d with same issuer", req->call, MC_state_get_internal_request(prev_state)->call);
-            break;
+              break;
 
-          }else{
+            }else if(req->issuer == MC_state_get_internal_request(prev_state)->issuer){
 
-            MC_state_remove_interleave_process(prev_state, req->issuer);
-            XBT_DEBUG("Simcall %d in process %lu independant with simcall %d process %lu", req->call, req->issuer->pid, MC_state_get_internal_request(prev_state)->call, MC_state_get_internal_request(prev_state)->issuer->pid);  
+              XBT_DEBUG("Simcall %d and %d with same issuer", req->call, MC_state_get_internal_request(prev_state)->call);
+              break;
 
+            }
           }
         }
-       
+             
         if (MC_state_interleave_size(state)) {
           /* We found a back-tracking point, let's loop */
           if(_sg_mc_checkpoint){
index 970ef80..562eb37 100644 (file)
@@ -406,11 +406,12 @@ void MC_replay(xbt_fifo_t stack, int start)
 {
   int raw_mem = (mmalloc_get_current_heap() == raw_heap);
 
-  int value, i = 1;
+  int value, i = 1, count = 1;
   char *req_str;
   smx_simcall_t req = NULL, saved_req = NULL;
   xbt_fifo_item_t item, start_item;
   mc_state_t state;
+  smx_process_t process = NULL;
 
   XBT_DEBUG("**** Begin Replay ****");
 
@@ -430,6 +431,19 @@ void MC_replay(xbt_fifo_t stack, int start)
     }
   }
 
+  MC_SET_RAW_MEM;
+  xbt_dict_reset(first_enabled_state);
+  xbt_swag_foreach(process, simix_global->process_list){
+    if(MC_process_is_enabled(process)){
+      char *key = bprintf("%lu", process->pid);
+      char *data = bprintf("%d", count);
+      xbt_dict_set(first_enabled_state, key, data, NULL);
+      xbt_free(key);
+    }
+  }
+  MC_UNSET_RAW_MEM;
+  
+
   /* Traverse the stack from the state at position start and re-execute the transitions */
   for (item = start_item;
        item != xbt_fifo_get_first_item(stack);
@@ -438,6 +452,12 @@ void MC_replay(xbt_fifo_t stack, int start)
     state = (mc_state_t) xbt_fifo_get_item_content(item);
     saved_req = MC_state_get_executed_request(state, &value);
    
+    MC_SET_RAW_MEM;
+    char *key = bprintf("%lu", saved_req->issuer->pid);
+    xbt_dict_remove(first_enabled_state, key); 
+    xbt_free(key);
+    MC_UNSET_RAW_MEM;
+   
     if(saved_req){
       /* because we got a copy of the executed request, we have to fetch the  
          real one, pointed by the request field of the issuer process */
@@ -450,14 +470,32 @@ void MC_replay(xbt_fifo_t stack, int start)
         xbt_free(req_str);
       }
     }
-         
+    
     SIMIX_simcall_pre(req, value);
     MC_wait_for_requests();
+
+    count++;
+
+    MC_SET_RAW_MEM;
+    /* Insert in dict all enabled processes */
+    xbt_swag_foreach(process, simix_global->process_list){
+      if(MC_process_is_enabled(process) /*&& !MC_state_process_is_done(state, process)*/){
+        char *key = bprintf("%lu", process->pid);
+        if(xbt_dict_get_or_null(first_enabled_state, key) == NULL){
+          char *data = bprintf("%d", count);
+          xbt_dict_set(first_enabled_state, key, data, NULL);
+        }
+        xbt_free(key);
+      }
+    }
+    MC_UNSET_RAW_MEM;
          
     /* Update statistics */
     mc_stats->visited_states++;
     mc_stats->executed_transitions++;
+
   }
+
   XBT_DEBUG("**** End Replay ****");
 
   if(raw_mem)
@@ -527,7 +565,7 @@ void MC_replay_liveness(xbt_fifo_t stack, int all_stack)
       depth++;
     
       /* Update statistics */
-      mc_stats->visited_states++;
+      mc_stats->visited_pairs++;
       mc_stats->executed_transitions++;
 
       item = xbt_fifo_get_prev_item(item);
@@ -570,7 +608,7 @@ void MC_replay_liveness(xbt_fifo_t stack, int all_stack)
       depth++;
     
       /* Update statistics */
-      mc_stats->visited_states++;
+      mc_stats->visited_pairs++;
       mc_stats->executed_transitions++;
     }
   }  
@@ -692,14 +730,14 @@ void MC_dump_stack_liveness(xbt_fifo_t stack){
 
 void MC_print_statistics(mc_stats_t stats)
 {
-  //XBT_INFO("State space size ~= %lu", stats->state_size);
-  XBT_INFO("Expanded states = %lu", stats->expanded_states);
-  XBT_INFO("Visited states = %lu", stats->visited_states);
+  if(stats->expanded_pairs == 0){
+    XBT_INFO("Expanded states = %lu", stats->expanded_states);
+    XBT_INFO("Visited states = %lu", stats->visited_states);
+  }else{
+    XBT_INFO("Expanded pairs = %lu", stats->expanded_pairs);
+    XBT_INFO("Visited pairs = %lu", stats->visited_pairs);
+  }
   XBT_INFO("Executed transitions = %lu", stats->executed_transitions);
-  XBT_INFO("Expanded / Visited = %lf",
-           (double) stats->visited_states / stats->expanded_states);
-  /*XBT_INFO("Exploration coverage = %lf",
-    (double)stats->expanded_states / stats->state_size); */
 }
 
 void MC_assert(int prop)
@@ -821,7 +859,7 @@ void MC_ignore_heap(void *address, size_t size){
   }
 
   unsigned int cursor = 0;
-  mc_heap_ignore_region_t current_region;
+  mc_heap_ignore_region_t current_region = NULL;
   int start = 0;
   int end = xbt_dynar_length(mc_heap_comparison_ignore) - 1;
   
index f19a670..362e331 100644 (file)
@@ -19,17 +19,15 @@ xbt_dynar_t successors;
 
 /********* Static functions *********/
 
-static int is_reached_acceptance_pair(xbt_automaton_state_t st){
-
-  int raw_mem_set = (mmalloc_get_current_heap() == raw_heap);
-
-  MC_SET_RAW_MEM;
+static mc_acceptance_pair_t acceptance_pair_new(int num, xbt_automaton_state_t as){
 
   mc_acceptance_pair_t new_pair = NULL;
   new_pair = xbt_new0(s_mc_acceptance_pair_t, 1);
-  new_pair->num = xbt_dynar_length(acceptance_pairs) + 1;
-  new_pair->automaton_state = st;
+  new_pair->num = num;
+  new_pair->automaton_state = as;
   new_pair->prop_ato = xbt_dynar_new(sizeof(int), NULL);
+  new_pair->heap_bytes_used = mmalloc_get_bytes_used(std_heap);
+  new_pair->nb_processes = xbt_swag_size(simix_global->process_list);
   new_pair->system_state = MC_take_snapshot();  
   
   /* Get values of propositional symbols */
@@ -42,105 +40,219 @@ static int is_reached_acceptance_pair(xbt_automaton_state_t st){
     res = f();
     xbt_dynar_push_as(new_pair->prop_ato, int, res);
   }
-  
+
+  return new_pair;
+
+}
+
+static int is_reached_acceptance_pair(int num, xbt_automaton_state_t as){
+
+  int raw_mem_set = (mmalloc_get_current_heap() == raw_heap);
+
+  MC_SET_RAW_MEM;
+  mc_acceptance_pair_t new_pair = acceptance_pair_new(num, as);  
   MC_UNSET_RAW_MEM;
   
   if(xbt_dynar_is_empty(acceptance_pairs)){
 
     MC_SET_RAW_MEM;
-    /* New acceptance pair */
     xbt_dynar_push(acceptance_pairs, &new_pair); 
     MC_UNSET_RAW_MEM;
 
     if(raw_mem_set)
       MC_SET_RAW_MEM;
-    return 0;
+
+    return -1;
 
   }else{
 
     MC_SET_RAW_MEM;
     
-    cursor = 0;
+    size_t current_bytes_used = new_pair->heap_bytes_used;
+    int current_nb_processes = new_pair->nb_processes;
+
+    unsigned int cursor = 0;
+    int previous_cursor = 0, next_cursor = 0;
+    int start = 0;
+    int end = xbt_dynar_length(acceptance_pairs) - 1;
+
     mc_acceptance_pair_t pair_test = NULL;
-     
-    xbt_dynar_foreach(acceptance_pairs, cursor, pair_test){
-      if(XBT_LOG_ISENABLED(mc_liveness, xbt_log_priority_debug))
-        XBT_DEBUG("****** Pair reached #%d ******", pair_test->num);
-      if(xbt_automaton_state_compare(pair_test->automaton_state, st) == 0){
-        if(xbt_automaton_propositional_symbols_compare_value(pair_test->prop_ato, new_pair->prop_ato) == 0){
-          if(snapshot_compare(new_pair->system_state, pair_test->system_state) == 0){
-            
-            if(raw_mem_set)
-              MC_SET_RAW_MEM;
-            else
-              MC_UNSET_RAW_MEM;
-            
-            return 1;
+    size_t bytes_used_test;
+    int nb_processes_test;
+    int same_processes_and_bytes_not_found = 1;
+
+    while(start <= end && same_processes_and_bytes_not_found){
+      cursor = (start + end) / 2;
+      pair_test = (mc_acceptance_pair_t)xbt_dynar_get_as(acceptance_pairs, cursor, mc_acceptance_pair_t);
+      bytes_used_test = pair_test->heap_bytes_used;
+      nb_processes_test = pair_test->nb_processes;
+      if(nb_processes_test < current_nb_processes)
+        start = cursor + 1;
+      if(nb_processes_test > current_nb_processes)
+        end = cursor - 1; 
+      if(nb_processes_test == current_nb_processes){
+        if(bytes_used_test < current_bytes_used)
+          start = cursor + 1;
+        if(bytes_used_test > current_bytes_used)
+          end = cursor - 1;
+        if(bytes_used_test == current_bytes_used){
+          same_processes_and_bytes_not_found = 0;
+          if(xbt_automaton_state_compare(pair_test->automaton_state, as) == 0){
+            if(xbt_automaton_propositional_symbols_compare_value(pair_test->prop_ato, new_pair->prop_ato) == 0){
+              if(snapshot_compare(new_pair->system_state, pair_test->system_state) == 0){
+                if(raw_mem_set)
+                  MC_SET_RAW_MEM;
+                else
+                  MC_UNSET_RAW_MEM;
+                return pair_test->num;
+              }
+            }
+          }
+          /* Search another pair with same number of bytes used in std_heap */
+          previous_cursor = cursor - 1;
+          while(previous_cursor >= 0){
+            pair_test = (mc_acceptance_pair_t)xbt_dynar_get_as(acceptance_pairs, previous_cursor, mc_acceptance_pair_t);
+            bytes_used_test = pair_test->system_state->heap_bytes_used;
+            if(bytes_used_test != current_bytes_used)
+              break;
+            if(xbt_automaton_state_compare(pair_test->automaton_state, as) == 0){
+              if(xbt_automaton_propositional_symbols_compare_value(pair_test->prop_ato, new_pair->prop_ato) == 0){  
+                if(snapshot_compare(new_pair->system_state, pair_test->system_state) == 0){
+                  if(raw_mem_set)
+                    MC_SET_RAW_MEM;
+                  else
+                    MC_UNSET_RAW_MEM;
+                  return pair_test->num;
+                }
+              }
+            }
+            previous_cursor--;
+          }
+          next_cursor = cursor + 1;
+          while(next_cursor < xbt_dynar_length(acceptance_pairs)){
+            pair_test = (mc_acceptance_pair_t)xbt_dynar_get_as(acceptance_pairs, next_cursor, mc_acceptance_pair_t);
+            bytes_used_test = pair_test->system_state->heap_bytes_used;
+            if(bytes_used_test != current_bytes_used)
+              break;
+            if(xbt_automaton_state_compare(pair_test->automaton_state, as) == 0){
+              if(xbt_automaton_propositional_symbols_compare_value(pair_test->prop_ato, new_pair->prop_ato) == 0){
+                if(snapshot_compare(new_pair->system_state, pair_test->system_state) == 0){
+                  if(raw_mem_set)
+                    MC_SET_RAW_MEM;
+                  else
+                    MC_UNSET_RAW_MEM;
+                  return pair_test->num;
+                }
+              }
+            }
+            next_cursor++;
           }
-        }else{
-          XBT_DEBUG("Different values of propositional symbols");
         }
-      }else{
-        XBT_DEBUG("Different automaton state");
       }
     }
 
-    /* New acceptance pair */
-    xbt_dynar_push(acceptance_pairs, &new_pair); 
+    pair_test = (mc_acceptance_pair_t)xbt_dynar_get_as(acceptance_pairs, cursor, mc_acceptance_pair_t);
+    bytes_used_test = pair_test->heap_bytes_used;
+
+    if(bytes_used_test < current_bytes_used)
+      xbt_dynar_insert_at(acceptance_pairs, cursor + 1, &new_pair);
+    else
+      xbt_dynar_insert_at(acceptance_pairs, cursor, &new_pair);
     
     MC_UNSET_RAW_MEM;
 
     if(raw_mem_set)
       MC_SET_RAW_MEM;
-    compare = 0;
     
-    return 0;
+    return -1;
     
   }
 }
 
 
-static void set_acceptance_pair_reached(xbt_automaton_state_t st){
+static void set_acceptance_pair_reached(int num, xbt_automaton_state_t as){
 
   int raw_mem_set = (mmalloc_get_current_heap() == raw_heap);
  
   MC_SET_RAW_MEM;
+  mc_acceptance_pair_t new_pair = acceptance_pair_new(num, as);
+  MC_UNSET_RAW_MEM;
 
-  mc_acceptance_pair_t pair = NULL;
-  pair = xbt_new0(s_mc_acceptance_pair_t, 1);
-  pair->num = xbt_dynar_length(acceptance_pairs) + 1;
-  pair->automaton_state = st;
-  pair->prop_ato = xbt_dynar_new(sizeof(int), NULL);
-  pair->system_state = MC_take_snapshot();
+  if(xbt_dynar_is_empty(acceptance_pairs)){
 
-  /* Get values of propositional symbols */
-  unsigned int cursor = 0;
-  xbt_automaton_propositional_symbol_t ps = NULL;
-  int res;
-  int_f_void_t f;
+     MC_SET_RAW_MEM;
+     xbt_dynar_push(acceptance_pairs, &new_pair); 
+     MC_UNSET_RAW_MEM;
 
-  xbt_dynar_foreach(_mc_property_automaton->propositional_symbols, cursor, ps){
-    f = (int_f_void_t)ps->function;
-    res = f();
-    xbt_dynar_push_as(pair->prop_ato, int, res);
-  }
+  }else{
 
-  xbt_dynar_push(acceptance_pairs, &pair); 
-  
-  MC_UNSET_RAW_MEM;
+    MC_SET_RAW_MEM;
+    
+    size_t current_bytes_used = new_pair->heap_bytes_used;
+    int current_nb_processes = new_pair->nb_processes;
+
+    unsigned int cursor = 0;
+    int start = 0;
+    int end = xbt_dynar_length(acceptance_pairs) - 1;
+
+    mc_acceptance_pair_t pair_test = NULL;
+    size_t bytes_used_test = 0;
+    int nb_processes_test;
+
+    while(start <= end){
+      cursor = (start + end) / 2;
+      pair_test = (mc_acceptance_pair_t)xbt_dynar_get_as(acceptance_pairs, cursor, mc_acceptance_pair_t);
+      bytes_used_test = pair_test->heap_bytes_used;
+      nb_processes_test = pair_test->nb_processes;
+      if(nb_processes_test < current_nb_processes)
+        start = cursor + 1;
+      if(nb_processes_test > current_nb_processes)
+        end = cursor - 1; 
+      if(nb_processes_test == current_nb_processes){
+        if(bytes_used_test < current_bytes_used)
+          start = cursor + 1;
+        if(bytes_used_test > current_bytes_used)
+          end = cursor - 1;
+        if(bytes_used_test == current_bytes_used)
+          break;
+      }
+    }
+
+    if(bytes_used_test < current_bytes_used)
+      xbt_dynar_insert_at(acceptance_pairs, cursor + 1, &new_pair);
+    else
+      xbt_dynar_insert_at(acceptance_pairs, cursor, &new_pair);
+    
+    MC_UNSET_RAW_MEM;
+    
+  }
 
   if(raw_mem_set)
     MC_SET_RAW_MEM;
     
 }
 
-static mc_visited_pair_t visited_pair_new(xbt_automaton_state_t as){
+static void remove_acceptance_pair(int num_pair){
+
+  unsigned int cursor = 0;
+  mc_acceptance_pair_t current_pair;
+
+  xbt_dynar_foreach(acceptance_pairs, cursor, current_pair){
+    if(current_pair->num == num_pair)
+      break;
+  }
+  
+  xbt_dynar_remove_at(acceptance_pairs, cursor, NULL);
+
+}
+
+static mc_visited_pair_t visited_pair_new(int num, xbt_automaton_state_t as){
 
   mc_visited_pair_t new_pair = NULL;
   new_pair = xbt_new0(s_mc_visited_pair_t, 1);
   new_pair->automaton_state = as;
+  new_pair->num = num;
   new_pair->prop_ato = xbt_dynar_new(sizeof(int), NULL);
   new_pair->heap_bytes_used = mmalloc_get_bytes_used(std_heap);
   new_pair->nb_processes = xbt_swag_size(simix_global->process_list);
@@ -161,7 +273,7 @@ static mc_visited_pair_t visited_pair_new(xbt_automaton_state_t as){
 
 }
 
-static int is_visited_pair(xbt_automaton_state_t as){
+static int is_visited_pair(int num, xbt_automaton_state_t as){
 
   if(_sg_mc_visited == 0)
     return -1;
@@ -169,7 +281,7 @@ static int is_visited_pair(xbt_automaton_state_t as){
   int raw_mem_set = (mmalloc_get_current_heap() == raw_heap);
 
   MC_SET_RAW_MEM;
-  mc_visited_pair_t new_pair = visited_pair_new(as);
+  mc_visited_pair_t new_pair = visited_pair_new(num, as);
   MC_UNSET_RAW_MEM;
 
   if(xbt_dynar_is_empty(visited_pairs)){
@@ -443,7 +555,7 @@ void MC_ddfs_init(void){
         xbt_fifo_unshift(mc_stack_liveness, mc_initial_pair);
         MC_UNSET_RAW_MEM;
 
-        set_acceptance_pair_reached(automaton_state);
+        set_acceptance_pair_reached(mc_initial_pair->num, automaton_state);
 
         if(cursor != 0){
           MC_restore_snapshot(initial_state_liveness->snapshot);
@@ -483,7 +595,7 @@ void MC_ddfs(int search_cycle){
  
   XBT_DEBUG("********************* ( Depth = %d, search_cycle = %d )", xbt_fifo_size(mc_stack_liveness), search_cycle);
  
-  mc_stats->visited_states++;
+  mc_stats->visited_pairs++;
 
   int value;
   mc_state_t next_graph_state = NULL;
@@ -498,7 +610,6 @@ void MC_ddfs(int search_cycle){
   mc_pair_t pair_succ;
 
   mc_pair_t pair_to_remove;
-  mc_acceptance_pair_t acceptance_pair_to_remove;
   
   if(xbt_fifo_size(mc_stack_liveness) < _sg_mc_max_depth){
 
@@ -583,7 +694,7 @@ void MC_ddfs(int search_cycle){
 
             if((pair_succ->automaton_state->type == 1) || (pair_succ->automaton_state->type == 2)){ 
           
-              if(is_reached_acceptance_pair(pair_succ->automaton_state)){
+              if(is_reached_acceptance_pair(pair_succ->num, pair_succ->automaton_state) != -1){
         
                 XBT_INFO("Next pair (depth = %d, %u interleave) already reached !", xbt_fifo_size(mc_stack_liveness) + 1, MC_state_interleave_size(pair_succ->graph_state));
 
@@ -598,7 +709,7 @@ void MC_ddfs(int search_cycle){
 
               }else{
 
-                if(is_visited_pair(pair_succ->automaton_state) != -1){
+                if(is_visited_pair(pair_succ->num, pair_succ->automaton_state) != -1){
 
                   XBT_DEBUG("Next pair already visited !");
                   break;
@@ -621,7 +732,7 @@ void MC_ddfs(int search_cycle){
 
             }else{
 
-              if(is_visited_pair(pair_succ->automaton_state) != -1){
+              if(is_visited_pair(pair_succ->num, pair_succ->automaton_state) != -1){
 
                 XBT_DEBUG("Next pair already visited !");
                 break;
@@ -639,7 +750,7 @@ void MC_ddfs(int search_cycle){
 
           }else{
 
-            if(is_visited_pair(pair_succ->automaton_state) != -1){
+            if(is_visited_pair(pair_succ->num, pair_succ->automaton_state) != -1){
 
               XBT_DEBUG("Next pair already visited !");
               break;
@@ -650,7 +761,7 @@ void MC_ddfs(int search_cycle){
 
                 XBT_DEBUG("Next pair (depth =%d) -> Acceptance pair (%s)", xbt_fifo_size(mc_stack_liveness) + 1, pair_succ->automaton_state->id);
       
-                set_acceptance_pair_reached(pair_succ->automaton_state); 
+                set_acceptance_pair_reached(pair_succ->num, pair_succ->automaton_state); 
 
                 search_cycle = 1;
 
@@ -734,7 +845,7 @@ void MC_ddfs(int search_cycle){
 
           if((pair_succ->automaton_state->type == 1) || (pair_succ->automaton_state->type == 2)){ 
 
-            if(is_reached_acceptance_pair(pair_succ->automaton_state)){
+            if(is_reached_acceptance_pair(pair_succ->num, pair_succ->automaton_state) != -1){
            
               XBT_INFO("Next pair (depth = %d) already reached !", xbt_fifo_size(mc_stack_liveness) + 1);
         
@@ -749,7 +860,7 @@ void MC_ddfs(int search_cycle){
 
             }else{
 
-              if(is_visited_pair(pair_succ->automaton_state) != -1){
+              if(is_visited_pair(pair_succ->num, pair_succ->automaton_state) != -1){
                 
                 XBT_DEBUG("Next pair already visited !");
                 break;
@@ -772,7 +883,7 @@ void MC_ddfs(int search_cycle){
 
           }else{
             
-            if(is_visited_pair(pair_succ->automaton_state) != -1){
+            if(is_visited_pair(pair_succ->num, pair_succ->automaton_state) != -1){
               
               XBT_DEBUG("Next pair already visited !");
               break;
@@ -792,7 +903,7 @@ void MC_ddfs(int search_cycle){
 
         }else{
       
-          if(is_visited_pair(pair_succ->automaton_state) != -1){
+          if(is_visited_pair(pair_succ->num, pair_succ->automaton_state) != -1){
 
             XBT_DEBUG("Next pair already visited !");
             break;
@@ -801,7 +912,7 @@ void MC_ddfs(int search_cycle){
 
             if(((pair_succ->automaton_state->type == 1) || (pair_succ->automaton_state->type == 2))){
 
-              set_acceptance_pair_reached(pair_succ->automaton_state);
+              set_acceptance_pair_reached(pair_succ->num, pair_succ->automaton_state);
          
               search_cycle = 1;
 
@@ -849,9 +960,7 @@ void MC_ddfs(int search_cycle){
   xbt_fifo_remove(mc_stack_liveness, pair_to_remove);
   pair_to_remove = NULL;
   if((current_pair->automaton_state->type == 1) || (current_pair->automaton_state->type == 2)){
-    acceptance_pair_to_remove = xbt_dynar_pop_as(acceptance_pairs, mc_acceptance_pair_t);
-    acceptance_pair_free(acceptance_pair_to_remove);
-    acceptance_pair_to_remove = NULL;
+    remove_acceptance_pair(current_pair->num);
   }
   MC_UNSET_RAW_MEM;
 
index 9e8ff3e..bd686f9 100644 (file)
@@ -12,6 +12,7 @@ mc_pair_t MC_pair_new(mc_state_t gs, xbt_automaton_state_t as, int r){
   p->graph_state = gs;
   p->system_state = NULL;
   p->requests = r;
+  p->num = ++mc_stats->expanded_pairs;
   return p;
 }
 
index 15deac2..55ac046 100644 (file)
@@ -140,7 +140,9 @@ void MC_state_remove_interleave_process(mc_state_t state, smx_process_t process)
 typedef struct mc_stats {
   unsigned long state_size;
   unsigned long visited_states;
+  unsigned long visited_pairs;
   unsigned long expanded_states;
+  unsigned long expanded_pairs;
   unsigned long executed_transitions;
 } s_mc_stats_t, *mc_stats_t;
 
@@ -259,6 +261,7 @@ typedef enum {
 extern e_mc_reduce_t mc_reduce_kind;
 extern mc_global_t initial_state_safety;
 extern xbt_fifo_t mc_stack_safety;
+extern xbt_dict_t first_enabled_state;
 
 void MC_dpor_init(void);
 void MC_dpor(void);
@@ -285,6 +288,7 @@ typedef struct s_mc_pair{
   mc_state_t graph_state;
   xbt_automaton_state_t automaton_state;
   int requests;
+  int num;
 }s_mc_pair_t, *mc_pair_t;
 
 typedef struct s_mc_acceptance_pair{
@@ -292,6 +296,8 @@ typedef struct s_mc_acceptance_pair{
   xbt_automaton_state_t automaton_state;
   xbt_dynar_t prop_ato;
   mc_snapshot_t system_state;
+  size_t heap_bytes_used;
+  int nb_processes;
 }s_mc_acceptance_pair_t, *mc_acceptance_pair_t;
 
 typedef struct s_mc_visited_pair{
index 5f88dc9..28fcdf7 100644 (file)
@@ -226,6 +226,35 @@ static void _sg_cfg_cb__weight_S(const char *name, int pos)
   sg_weight_S_parameter = xbt_cfg_get_double(_sg_cfg_set, name);
 }
 
+/* callback of the mpi collectives */
+static void _sg_cfg_cb__coll(char *category,
+                            s_mpi_coll_description_t * table,
+                            const char *name, int pos)
+{
+  char *val;
+
+  xbt_assert(_sg_init_status == 1,
+              "Cannot change the model after the initialization");
+
+  val = xbt_cfg_get_string(_sg_cfg_set, name);
+
+  if (!strcmp(val, "help")) {
+    coll_help(category, table);
+    exit(0);
+  }
+
+  /* New Module missing */
+  find_coll_description(table, val);
+}
+static void _sg_cfg_cb__coll_alltoall(const char *name, int pos)
+{
+  _sg_cfg_cb__coll("alltoall", mpi_coll_alltoall_description, name, pos);  
+}
+static void _sg_cfg_cb__coll_allgather(const char *name, int pos){
+  _sg_cfg_cb__coll("allgather", mpi_coll_allgather_description, name, pos);
+}
+
+
 /* callback of the inclusion path */
 static void _sg_cfg_cb__surf_path(const char *name, int pos)
 {
@@ -711,7 +740,17 @@ void sg_config_init(int *argc, char **argv)
                      NULL);
     xbt_cfg_setdefault_string(_sg_cfg_set, "smpi/or", "1:0:0:0:0");
 
-
+    default_value = xbt_strdup("ompi");    
+    xbt_cfg_register(&_sg_cfg_set, "smpi/alltoall",
+                    "Which collective to use for alltoall",
+                    xbt_cfgelm_string, &default_value, 1, 1, &_sg_cfg_cb__coll_alltoall,
+                    NULL);
+
+    default_value = xbt_strdup("default");    
+    xbt_cfg_register(&_sg_cfg_set, "smpi/allgather",
+                    "Which collective to use for allgather",
+                    xbt_cfgelm_string, &default_value, 1, 1, &_sg_cfg_cb__coll_allgather,
+                    NULL);
     //END SMPI
 
 
diff --git a/src/smpi/colls/COPYRIGHTS b/src/smpi/colls/COPYRIGHTS
new file mode 100644 (file)
index 0000000..97b85eb
--- /dev/null
@@ -0,0 +1,39 @@
+Copyright (c) 2006, Ahmad Faraj & Xin Yuan,
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+  * Redistributions of source code must retain the above copyright notice,
+    this list of conditions and the following disclaimer.
+
+  * Redistributions in binary form must reproduce the above copyright notice,
+    this list of conditions and the following disclaimer in the documentation
+    and/or other materials provided with the distribution.
+
+  * Neither the name of the Florida State University nor the names of its
+    contributors may be used to endorse or promote products derived from this
+    software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
+ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+  ***************************************************************************
+  *     Any results obtained from executing this software require the       *
+  *     acknowledgment and citation of the software and its owners.         *
+  *     The full citation is given below:                                   *
+  *                                                                         *
+  *     A. Faraj, X. Yuan, and D. Lowenthal. "STAR-MPI: Self Tuned Adaptive *
+  *     Routines for MPI Collective Operations." The 20th ACM International *
+  *     Conference on Supercomputing (ICS), Queensland, Australia           *
+  *     June 28-July 1, 2006.                                               *
+  ***************************************************************************
+
diff --git a/src/smpi/colls/alltoall-2dmesh.c b/src/smpi/colls/alltoall-2dmesh.c
new file mode 100644 (file)
index 0000000..1e1e408
--- /dev/null
@@ -0,0 +1,204 @@
+#include "colls.h"
+#include <math.h>
+XBT_LOG_NEW_DEFAULT_SUBCATEGORY(smpi_colls, smpi,
+                                "Logging specific to SMPI collectives");
+
+/*****************************************************************************
+
+ * Function: alltoall_2dmesh_shoot
+
+ * Return: int
+
+ * Inputs:
+    send_buff: send input buffer
+    send_count: number of elements to send
+    send_type: data type of elements being sent
+    recv_buff: receive output buffer
+    recv_count: number of elements to received
+    recv_type: data type of elements being received
+    comm: communicator
+
+ * Descrp: Function realizes the alltoall operation using the 2dmesh
+           algorithm. It actually performs allgather operation in x dimension
+           then in the y dimension. Each node then extracts the needed data.
+           The communication in each dimension follows "simple."
+ * Auther: Ahmad Faraj
+
+****************************************************************************/
+int alltoall_check_is_2dmesh(int num, int * i, int * j)
+{
+  int x, max = num / 2;
+  x = sqrt(num);  
+
+  while (x <= max)
+    {
+      if ((num % x) == 0)
+       {
+         * i = x;
+         * j = num / x;
+       
+         if (* i > * j)
+           {
+             x = * i;
+             * i = * j;
+             * j = x;
+           }
+       
+         return 1;
+       }
+      x++;
+    }
+  return 0;
+}
+
+int
+smpi_coll_tuned_alltoall_2dmesh(void * send_buff, int send_count, MPI_Datatype send_type,
+                     void * recv_buff, int recv_count, MPI_Datatype recv_type,
+                     MPI_Comm comm)
+{
+  MPI_Status * statuses, s;
+  MPI_Request * reqs, * req_ptr;;
+  MPI_Aint extent;
+
+  char * tmp_buff1, * tmp_buff2;
+  int i, j, src, dst, rank, num_procs, count, num_reqs;
+  int rows, cols, my_row, my_col, X, Y, send_offset, recv_offset;
+  int two_dsize, my_row_base, my_col_base, src_row_base, block_size;
+  int tag = 1, failure = 0, success = 1;
+  
+  MPI_Comm_rank(comm, &rank);
+  MPI_Comm_size(comm, &num_procs);
+  MPI_Type_extent(send_type, &extent);
+
+  if (!alltoall_check_is_2dmesh(num_procs, &X, &Y))
+    return failure;
+
+  two_dsize = X * Y;
+
+  my_row_base = (rank / Y) * Y;
+  my_col_base = rank % Y;
+
+  block_size = extent * send_count;
+  
+  tmp_buff1 =(char *) malloc(block_size * num_procs * Y);
+  if (!tmp_buff1)
+    {
+      XBT_DEBUG("alltoall-2dmesh_shoot.c:88: cannot allocate memory");
+      MPI_Finalize();
+      exit(failure);
+    }  
+
+  tmp_buff2 =(char *) malloc(block_size *  Y);  
+  if (!tmp_buff2)
+    {
+      XBT_WARN("alltoall-2dmesh_shoot.c:88: cannot allocate memory");
+      MPI_Finalize();
+      exit(failure);
+    }
+  
+
+
+  num_reqs = X;
+  if (Y > X) num_reqs = Y;
+
+  statuses = (MPI_Status *) malloc(num_reqs * sizeof(MPI_Status));  
+  reqs = (MPI_Request *) malloc(num_reqs * sizeof(MPI_Request));  
+  if (!reqs)
+    {
+      XBT_WARN("alltoall-2dmesh_shoot.c:88: cannot allocate memory");
+      MPI_Finalize();
+      exit(failure);
+    }
+  
+  req_ptr = reqs;
+
+  send_offset = recv_offset = (rank % Y) * block_size * num_procs;
+
+  count = send_count * num_procs;
+  
+  for (i = 0; i < Y; i++)
+    {
+      src = i + my_row_base;
+      if (src == rank)
+       continue;
+
+      recv_offset = (src % Y) * block_size * num_procs;
+       MPI_Irecv(tmp_buff1 + recv_offset, count, recv_type, src, tag, comm,
+                req_ptr++);
+    }
+  
+  for (i = 0; i < Y; i++)
+    {
+      dst = i + my_row_base;
+      if (dst == rank)
+       continue;
+       MPI_Send(send_buff, count, send_type, dst, tag, comm);
+    }
+  
+  MPI_Waitall(Y - 1, reqs, statuses);
+  req_ptr = reqs;
+  
+  for (i = 0; i < Y; i++)
+    {
+      send_offset = (rank * block_size) + (i * block_size * num_procs);
+      recv_offset = (my_row_base * block_size) + (i * block_size);
+     
+      if (i + my_row_base == rank) 
+       MPI_Sendrecv (send_buff + recv_offset, send_count, send_type,
+                     rank, tag, recv_buff + recv_offset, recv_count,
+                     recv_type, rank, tag, comm, &s);
+
+     else 
+         MPI_Sendrecv (tmp_buff1 + send_offset, send_count, send_type,
+                      rank, tag, 
+                      recv_buff + recv_offset, recv_count, recv_type,
+                      rank, tag, comm, &s);
+    }
+
+  
+  for (i = 0; i < X; i++)
+  {
+     src = (i * Y + my_col_base);
+     if (src == rank)
+       continue;
+     src_row_base = (src / Y) * Y;
+
+      MPI_Irecv(recv_buff + src_row_base * block_size, recv_count * Y,
+               recv_type, src, tag, comm, req_ptr++);
+  }
+  
+  for (i = 0; i < X; i++)
+    {
+      dst = (i * Y + my_col_base);
+      if (dst == rank)
+       continue;
+
+      recv_offset = 0;
+      for (j = 0; j < Y; j++)
+       {
+         send_offset = (dst + j * num_procs) * block_size;
+
+         if (j + my_row_base == rank) 
+            MPI_Sendrecv (send_buff + dst * block_size, send_count, send_type,
+                          rank, tag, 
+                          tmp_buff2 + recv_offset, recv_count, recv_type,
+                          rank, tag, comm, &s);
+         else
+            MPI_Sendrecv (tmp_buff1 + send_offset, send_count, send_type,
+                          rank, tag, 
+                          tmp_buff2 + recv_offset, recv_count, recv_type,
+                          rank, tag, comm, &s);
+         
+         recv_offset += block_size;
+       }
+
+       MPI_Send(tmp_buff2, send_count * Y, send_type, dst, tag, comm);
+    }
+  MPI_Waitall(X - 1, reqs, statuses);
+  free(reqs);
+  free(statuses);
+  free(tmp_buff1);
+  free(tmp_buff2);  
+  return success;
+}
diff --git a/src/smpi/colls/alltoall-3dmesh.c b/src/smpi/colls/alltoall-3dmesh.c
new file mode 100644 (file)
index 0000000..afd47ce
--- /dev/null
@@ -0,0 +1,203 @@
+#include "colls.h"
+#include <math.h>
+
+/*****************************************************************************
+
+ * Function: alltoall_3dmesh_shoot
+
+ * Return: int
+
+ * Inputs:
+    send_buff: send input buffer
+    send_count: number of elements to send
+    send_type: data type of elements being sent
+    recv_buff: receive output buffer
+    recv_count: number of elements to received
+    recv_type: data type of elements being received
+    comm: communicator
+
+ * Descrp: Function realizes the alltoall operation using the 3dmesh
+           algorithm. It actually performs allgather operation in x dimension,
+           y dimension, then in z dimension. Each node then extracts the
+           needed data. The communication in all dimension is simple.
+
+ * Auther: Ahmad Faraj
+****************************************************************************/
+
+int alltoall_check_is_3dmesh(int num, int * i, int * j, int * k)
+{
+  int x, max = num / 3;
+  x = cbrt(num);  
+  * i = * j = * k = 0;
+  while (x <= max)
+    {
+      if ((num % (x * x)) == 0)
+       {
+         * i = * j = x;
+         * k = num / (x * x);
+         return 1;
+       }
+      x++;
+    }
+  return 0;
+}
+
+int smpi_coll_tuned_alltoall_3dmesh(void * send_buff, int send_count, MPI_Datatype send_type,
+                     void * recv_buff, int recv_count, MPI_Datatype recv_type,
+                     MPI_Comm comm)
+{
+  MPI_Request * reqs, * req_ptr;
+  MPI_Aint extent;
+  MPI_Status status, * statuses;
+  int i, j, src, dst, rank, num_procs, num_reqs, X, Y, Z, block_size, count;
+  int my_z, two_dsize, my_row_base, my_col_base, my_z_base, src_row_base;
+  int src_z_base, send_offset, recv_offset, tag = 1, failure = 0, success = 1;
+
+  char * tmp_buff1, * tmp_buff2;
+
+  MPI_Comm_rank(comm, &rank);
+  MPI_Comm_size(comm, &num_procs);
+  MPI_Type_extent(send_type, &extent);
+
+  if (!alltoall_check_is_3dmesh(num_procs, &X, &Y, &Z))
+     return failure;
+
+  num_reqs = X;
+  if (Y > X) num_reqs = Y;
+  if (Z > Y) num_reqs = Z;
+
+  two_dsize = X * Y;
+  my_z = rank / two_dsize;  
+
+  my_row_base = (rank / X) * X;
+  my_col_base = (rank % Y) + (my_z * two_dsize);
+  my_z_base = my_z * two_dsize;
+
+  block_size = extent * send_count;
+
+  tmp_buff1 =(char *) malloc(block_size * num_procs * two_dsize);
+  if (!tmp_buff1)
+    {
+      printf("alltoall-3Dmesh:97: cannot allocate memory\n");
+      MPI_Finalize();
+      exit(failure);
+    }
+  
+  tmp_buff2 =(char *) malloc(block_size *  two_dsize);
+  if (!tmp_buff2)
+    {
+      printf("alltoall-3Dmesh:105: cannot allocate memory\n");
+      MPI_Finalize();
+      exit(failure);
+    }
+  
+  statuses = (MPI_Status *) malloc(num_reqs * sizeof(MPI_Status));  
+  reqs = (MPI_Request *) malloc(num_reqs * sizeof(MPI_Request));  
+  if (!reqs)
+    {
+      printf("alltoall-3Dmesh:113: cannot allocate memory\n");
+      MPI_Finalize();
+      exit(failure);
+    }
+  
+  req_ptr = reqs;
+  
+  send_offset = recv_offset = (rank % two_dsize) * block_size * num_procs;
+
+  MPI_Sendrecv(send_buff, send_count * num_procs, send_type, rank, tag, 
+              tmp_buff1 + recv_offset, num_procs * recv_count,
+              recv_type, rank, tag, comm, &status);
+
+  count = send_count * num_procs;
+
+  for (i = 0; i < Y; i++)
+    {
+      src = i + my_row_base;
+      if (src == rank) continue;
+      recv_offset = (src % two_dsize) * block_size * num_procs;
+      MPI_Irecv(tmp_buff1 + recv_offset, count, recv_type, src, tag, comm,
+               req_ptr++);
+    }
+
+  for (i = 0; i < Y; i++)
+    {
+      dst = i + my_row_base;
+      if (dst == rank) continue;
+      MPI_Send(send_buff, count, send_type, dst, tag, comm);
+    }  
+
+  MPI_Waitall(Y - 1, reqs, statuses);
+  req_ptr = reqs;
+  
+
+  for (i = 0; i < X; i++)
+    {
+      src = (i * Y + my_col_base);
+      if (src == rank) continue;
+     
+      src_row_base = (src / X) * X;
+
+      recv_offset = (src_row_base % two_dsize) * block_size * num_procs;
+      MPI_Irecv(tmp_buff1 + recv_offset, recv_count * num_procs * Y,
+                recv_type, src, tag, comm, req_ptr++);
+    }
+
+  send_offset = (my_row_base % two_dsize) * block_size * num_procs;  
+  for (i = 0; i < X; i++)
+    {
+      dst = (i * Y + my_col_base);
+      if (dst == rank) continue;
+      MPI_Send(tmp_buff1 + send_offset, send_count * num_procs * Y, send_type,
+               dst, tag, comm);
+    }
+  
+  MPI_Waitall(X - 1, reqs, statuses);
+  req_ptr = reqs;
+
+  for (i = 0; i < two_dsize; i++)
+    {
+      send_offset = (rank * block_size) + (i * block_size * num_procs);
+      recv_offset = (my_z_base * block_size) + (i * block_size);
+      MPI_Sendrecv(tmp_buff1 + send_offset, send_count, send_type, rank, tag,
+                  recv_buff + recv_offset, recv_count, recv_type, rank, tag,
+                  comm, &status);
+    }  
+
+  for (i = 1; i < Z; i++)
+    {
+      src = (rank + i * two_dsize) % num_procs;
+      src_z_base = (src / two_dsize) * two_dsize;
+
+      recv_offset = (src_z_base * block_size);
+
+      MPI_Irecv(recv_buff + recv_offset, recv_count * two_dsize, recv_type,
+                src, tag, comm, req_ptr++);
+  }
+
+  for (i = 1; i < Z; i++)
+    {
+      dst = (rank + i * two_dsize) % num_procs;
+     
+      recv_offset = 0;
+      for (j = 0; j < two_dsize; j++)
+       {
+         send_offset = (dst + j * num_procs) * block_size;
+         MPI_Sendrecv(tmp_buff1 + send_offset, send_count, send_type,
+                      rank, tag, tmp_buff2 + recv_offset, recv_count,
+                      recv_type, rank, tag, comm, &status);
+         
+         recv_offset += block_size;
+       }
+
+      MPI_Send(tmp_buff2, send_count * two_dsize, send_type, dst, tag, comm);
+      
+    }
+  
+  MPI_Waitall(Z - 1, reqs, statuses);
+
+  free(reqs);
+  free(statuses);
+  free(tmp_buff1);
+  free(tmp_buff2);
+  return success;
+}
diff --git a/src/smpi/colls/alltoall-bruck.c b/src/smpi/colls/alltoall-bruck.c
new file mode 100644 (file)
index 0000000..5745f2f
--- /dev/null
@@ -0,0 +1,131 @@
+/*****************************************************************************
+
+ * Function: alltoall_bruck
+
+ * Return: int
+
+ * inputs:
+    send_buff: send input buffer
+    send_count: number of elements to send
+    send_type: data type of elements being sent
+    recv_buff: receive output buffer
+    recv_count: number of elements to received
+    recv_type: data type of elements being received
+    comm: communicator
+
+ * Descrp: Function realizes the alltoall operation using the bruck algorithm.
+
+ * Auther: MPICH / modified by Ahmad Faraj
+
+ ****************************************************************************/
+int
+smpi_coll_tuned_alltoall_bruck(void * send_buff, int send_count, MPI_Datatype send_type,
+              void * recv_buff, int recv_count, MPI_Datatype recv_type,
+              MPI_Comm comm)
+{
+  MPI_Status status;
+  MPI_Aint extent;
+  MPI_Datatype new_type;
+  int * blocks_length, * disps;
+  int i, src, dst, rank, num_procs, count, remainder, block, position;
+  int pack_size, tag = 1, pof2 = 1, success = 1, failure = 0;
+  
+
+  char * tmp_buff;  
+  char * send_ptr = (char *) send_buff;
+  char * recv_ptr = (char *) recv_buff;
+
+  MPI_Comm_size(comm, &num_procs);
+  MPI_Comm_rank(comm, &rank);
+
+  MPI_Type_extent(recv_type, &extent);
+
+  tmp_buff = (char *) malloc (num_procs * recv_count * extent); 
+  if (!tmp_buff)
+    {
+      printf("alltoall-bruck:53: cannot allocate memory\n");
+      MPI_Finalize();
+      exit(failure);
+    }
+
+  disps = (int *) malloc(sizeof(int) * num_procs);
+  if (!disps)
+    {
+      printf("alltoall-bruck:61: cannot allocate memory\n");
+      MPI_Finalize();
+      exit(failure);
+    }
+  
+  blocks_length = (int *) malloc(sizeof(int) * num_procs);  
+  if (!blocks_length)
+    {
+      printf("alltoall-bruck:69: cannot allocate memory\n");
+      MPI_Finalize();
+      exit(failure);
+    }
+
+  
+  MPI_Sendrecv(send_ptr + rank * send_count * extent,
+               (num_procs - rank) * send_count, send_type, rank, tag,
+               recv_ptr, (num_procs - rank) * recv_count, recv_type, rank,
+               tag, comm, &status);
+
+  MPI_Sendrecv(send_ptr, rank * send_count, send_type, rank, tag,
+               recv_ptr + (num_procs - rank) * recv_count * extent,
+               rank * recv_count, recv_type, rank, tag, comm, &status);  
+
+
+
+  MPI_Pack_size(send_count * num_procs, send_type, comm, &pack_size); 
+
+  while (pof2 < num_procs)
+    {
+      dst = (rank + pof2) % num_procs;
+      src = (rank - pof2 + num_procs) % num_procs;
+
+              
+      count = 0;
+      for (block = 1; block < num_procs; block++)
+       if (block & pof2) 
+         {
+           blocks_length[count] = send_count;
+           disps[count] = block * send_count;
+           count++;
+         }
+          
+      MPI_Type_indexed(count, blocks_length, disps, recv_type, &new_type);
+      MPI_Type_commit(&new_type);
+      
+      position = 0;
+      MPI_Pack(recv_buff, 1, new_type, tmp_buff, pack_size, &position, comm);
+      
+      MPI_Sendrecv(tmp_buff, position, MPI_PACKED, dst, tag, recv_buff, 1,
+                   new_type, src, tag, comm, &status);
+      MPI_Type_free(&new_type);
+      
+      pof2 *= 2;
+    }
+
+  free(disps);
+  free(blocks_length);
+  
+  MPI_Sendrecv(recv_ptr + (rank + 1) * recv_count * extent,
+              (num_procs - rank - 1) * recv_count, send_type,
+               rank, tag, tmp_buff, (num_procs - rank - 1) * recv_count,
+               recv_type, rank, tag, comm, &status);
+  
+  MPI_Sendrecv(recv_ptr, (rank + 1) * recv_count, send_type, rank, tag,
+               tmp_buff + (num_procs - rank - 1) * recv_count * extent,
+               (rank + 1) * recv_count, recv_type, rank, tag, comm, &status);
+
+      
+  for (i = 0; i < num_procs; i++) 
+    MPI_Sendrecv(tmp_buff + i * recv_count * extent, recv_count, send_type,
+                 rank, tag,
+                 recv_ptr + (num_procs - i - 1) * recv_count * extent,
+                 recv_count, recv_type, rank, tag, comm, &status);
+
+  free(tmp_buff);
+  return success;
+}
diff --git a/src/smpi/colls/alltoall-native.c b/src/smpi/colls/alltoall-native.c
new file mode 100644 (file)
index 0000000..8f6137b
--- /dev/null
@@ -0,0 +1,9 @@
+int
+alltoall_native(void * send_buff, int send_count,
+               MPI_Datatype send_type, void * recv_buff,
+               int recv_count, MPI_Datatype recv_type,
+               MPI_Comm comm)
+{
+  return MPI_Alltoall(send_buff, send_count, send_type, recv_buff, recv_count,
+                     recv_type, comm);
+}
diff --git a/src/smpi/colls/alltoall-pair-light-barrier.c b/src/smpi/colls/alltoall-pair-light-barrier.c
new file mode 100644 (file)
index 0000000..e6ab92a
--- /dev/null
@@ -0,0 +1,68 @@
+#include "colls.h"
+/*****************************************************************************
+
+ * Function: alltoall_pair_light_barrier
+
+ * Return: int
+
+ * Inputs:
+    send_buff: send input buffer
+    send_count: number of elements to send
+    send_type: data type of elements being sent
+    recv_buff: receive output buffer
+    recv_count: number of elements to received
+    recv_type: data type of elements being received
+    comm: communicator
+
+ * Descrp: Function works in P - 1 steps. In step i, node j exchanges data
+           with node i ^ j. Light barriers are inserted between
+           communications in different phases.
+
+ * Auther: Ahmad Faraj
+
+ ****************************************************************************/
+int
+smpi_coll_tuned_alltoall_pair_light_barrier(void * send_buff, int send_count,
+                           MPI_Datatype send_type, void * recv_buff,
+                           int recv_count, MPI_Datatype recv_type,
+                           MPI_Comm comm)
+{
+  MPI_Aint send_chunk, recv_chunk;
+  MPI_Status s;
+  int i, src, dst, rank, num_procs, next_partner;
+  int tag = 1, success = 1; /*, failure = 0;*/
+
+  char send_sync = 'a', recv_sync = 'b';
+  char * send_ptr = (char *) send_buff;
+  char * recv_ptr = (char *) recv_buff;
+  
+  MPI_Comm_rank(comm, &rank);
+  MPI_Comm_size(comm, &num_procs);
+  MPI_Type_extent(send_type, &send_chunk);
+  MPI_Type_extent(recv_type, &recv_chunk);
+
+  send_chunk *= send_count;
+  recv_chunk *= recv_count;
+
+  MPI_Sendrecv(send_ptr + rank * send_chunk, send_count, send_type, rank, tag,
+              recv_ptr + rank * recv_chunk, recv_count, recv_type, rank, tag,
+              comm, &s);
+
+  for (i = 1; i < num_procs; i++)
+    {
+      src = dst = rank ^ i;
+      
+      MPI_Sendrecv(send_ptr + dst * send_chunk, send_count, send_type,
+                  dst, tag, recv_ptr + src * recv_chunk, recv_count,
+                  recv_type, src, tag, comm, &s);
+
+      if ((i + 1) < num_procs)
+       {
+         next_partner = rank ^ (i + 1);
+         MPI_Sendrecv(&send_sync, 1, MPI_CHAR, next_partner, tag,
+                      &recv_sync, 1, MPI_CHAR, next_partner, tag,
+                      comm, &s);       
+       }
+    }
+  return success;
+}
diff --git a/src/smpi/colls/alltoall-pair-mpi-barrier.c b/src/smpi/colls/alltoall-pair-mpi-barrier.c
new file mode 100644 (file)
index 0000000..fcad564
--- /dev/null
@@ -0,0 +1,54 @@
+#include "colls.h"
+/*****************************************************************************
+
+ * Function: alltoall_pair_mpi_barrier
+
+ * Return: int
+
+ * Inputs:
+    send_buff: send input buffer
+    send_count: number of elements to send
+    send_type: data type of elements being sent
+    recv_buff: receive output buffer
+    recv_count: number of elements to received
+    recv_type: data type of elements being received
+    comm: communicator
+
+ * Descrp: Function works when P is power of two. In each phase of P - 1
+           phases, nodes in pair communicate their data. MPI barriers are
+           inserted between each two phases.
+
+ * Auther: Ahmad Faraj
+
+ ****************************************************************************/
+int
+smpi_coll_tuned_alltoall_pair_mpi_barrier(void * send_buff, int send_count,
+                         MPI_Datatype send_type, void * recv_buff,
+                         int recv_count, MPI_Datatype recv_type,
+                         MPI_Comm comm)
+{
+  MPI_Status s;
+  MPI_Aint send_chunk, recv_chunk;
+  int i, src, dst, rank, num_procs;
+  int tag = 101, success = 1; /*, failure = 0, pof2 = 1;*/
+  char * send_ptr = (char *) send_buff;
+  char * recv_ptr = (char *) recv_buff;
+  
+  MPI_Comm_rank(comm, &rank);
+  MPI_Comm_size(comm, &num_procs);
+  MPI_Type_extent(send_type, &send_chunk);
+  MPI_Type_extent(recv_type, &recv_chunk);
+
+  send_chunk *= send_count;
+  recv_chunk *= recv_count;  
+
+  for (i = 0; i < num_procs; i++)
+    {
+      src = dst = rank ^ i;     
+      MPI_Barrier(comm);      
+      MPI_Sendrecv(send_ptr + dst * send_chunk, send_count, send_type, dst,
+                  tag, recv_ptr + src * recv_chunk, recv_count, recv_type,
+                  src, tag, comm, &s);
+    }
+  return success;
+}
diff --git a/src/smpi/colls/alltoall-pair-one-barrier.c b/src/smpi/colls/alltoall-pair-one-barrier.c
new file mode 100644 (file)
index 0000000..478b881
--- /dev/null
@@ -0,0 +1,55 @@
+#include "colls.h"
+/*****************************************************************************
+
+ * Function: alltoall_pair
+
+ * Return: int
+
+ * Inputs:
+    send_buff: send input buffer
+    send_count: number of elements to send
+    send_type: data type of elements being sent
+    recv_buff: receive output buffer
+    recv_count: number of elements to received
+    recv_type: data type of elements being received
+    comm: communicator
+
+ * Descrp: Function works when P is power of two. In each phase of P - 1
+           phases, nodes in pair communicate their data.
+
+ * Auther: Ahmad Faraj
+
+ ****************************************************************************/
+int
+smpi_coll_tuned_alltoall_pair_one_barrier(void * send_buff, int send_count, MPI_Datatype send_type,
+                         void * recv_buff, int recv_count, MPI_Datatype recv_type,
+                         MPI_Comm comm)
+{
+
+  MPI_Aint send_chunk, recv_chunk;
+  MPI_Status s;
+  int i, src, dst, rank, num_procs;
+  int tag = 1, success = 1; /*, failure = 0, pof2 = 1; */
+
+  char * send_ptr = (char *) send_buff;
+  char * recv_ptr = (char *) recv_buff;
+  
+  MPI_Comm_rank(comm, &rank);
+  MPI_Comm_size(comm, &num_procs);
+  MPI_Type_extent(send_type, &send_chunk);
+  MPI_Type_extent(recv_type, &recv_chunk);
+
+  send_chunk *= send_count;
+  recv_chunk *= recv_count;  
+
+  MPI_Barrier(comm);
+  for (i = 0; i < num_procs; i++)
+    {
+      src = dst = rank ^ i;     
+      MPI_Sendrecv(send_ptr + dst * send_chunk, send_count, send_type, dst,
+                  tag, recv_ptr + src * recv_chunk, recv_count, recv_type,
+                  src, tag, comm, &s);
+    }
+
+  return success;
+}
diff --git a/src/smpi/colls/alltoall-pair.c b/src/smpi/colls/alltoall-pair.c
new file mode 100644 (file)
index 0000000..83658e0
--- /dev/null
@@ -0,0 +1,95 @@
+#include "smpi/mpi.h"
+/*****************************************************************************
+
+ * Function: alltoall_pair
+
+ * Return: int
+
+ * Inputs:
+    send_buff: send input buffer
+    send_count: number of elements to send
+    send_type: data type of elements being sent
+    recv_buff: receive output buffer
+    recv_count: number of elements to received
+    recv_type: data type of elements being received
+    comm: communicator
+
+ * Descrp: Function works when P is power of two. In each phase of P - 1
+           phases, nodes in pair communicate their data.
+
+ * Auther: Ahmad Faraj
+
+ ****************************************************************************/
+/*
+int
+alltoall_pair(void * send_buff, int send_count, MPI_Datatype send_type,
+             void * recv_buff, int recv_count, MPI_Datatype recv_type,
+             MPI_Comm comm)
+{
+
+  MPI_Aint send_chunk, recv_chunk;
+  MPI_Status s;
+  MPI_Win win;
+  int assert = 0;
+  int i, src, dst, rank, num_procs;
+  int tag = 1, success = 1, failure = 0, pof2 = 1;
+
+  char * send_ptr = (char *) send_buff;
+  char * recv_ptr = (char *) recv_buff;
+  
+  MPI_Comm_rank(comm, &rank);
+  MPI_Comm_size(comm, &num_procs);
+  MPI_Type_extent(send_type, &send_chunk);
+  MPI_Type_extent(recv_type, &recv_chunk);
+
+  MPI_Win_create(recv_buff, num_procs*recv_chunk*send_count,recv_chunk,0,
+                comm, &win);
+  send_chunk *= send_count;
+  recv_chunk *= recv_count;  
+
+  MPI_Win_fence(assert, win);
+  for (i = 0; i < num_procs; i++)
+    {
+      src = dst = rank ^ i;
+      MPI_Put(send_ptr + dst * send_chunk, send_count, send_type, dst,
+             rank*send_chunk, send_count, send_type, win);
+    }
+  MPI_Win_fence (assert, win);
+  MPI_Win_free(&win);
+  return 0;
+}
+*/
+
+int
+smpi_coll_tuned_alltoall_pair(void * send_buff, int send_count, MPI_Datatype send_type,
+             void * recv_buff, int recv_count, MPI_Datatype recv_type,
+             MPI_Comm comm)
+{
+
+  MPI_Aint send_chunk, recv_chunk;
+  MPI_Status s;
+  int i, src, dst, rank, num_procs;
+  int tag = 1, success = 1;
+
+  char * send_ptr = (char *) send_buff;
+  char * recv_ptr = (char *) recv_buff;
+  
+  MPI_Comm_rank(comm, &rank);
+  MPI_Comm_size(comm, &num_procs);
+  MPI_Type_extent(send_type, &send_chunk);
+  MPI_Type_extent(recv_type, &recv_chunk);
+
+  send_chunk *= send_count;
+  recv_chunk *= recv_count;  
+
+  for (i = 0; i < num_procs; i++)
+    {
+      src = dst = rank ^ i;     
+      MPI_Sendrecv(send_ptr + dst * send_chunk, send_count, send_type, dst,
+                  tag, recv_ptr + src * recv_chunk, recv_count, recv_type,
+                  src, tag, comm, &s);
+    }
+
+  return success;
+}
+
diff --git a/src/smpi/colls/alltoall-rdb.c b/src/smpi/colls/alltoall-rdb.c
new file mode 100644 (file)
index 0000000..b5bd8a5
--- /dev/null
@@ -0,0 +1,160 @@
+#include "colls.h"
+/*****************************************************************************
+
+ * Function: alltoall_rdb
+
+ * Return: int
+
+ * inputs: 
+    send_buff: send input buffer
+    send_count: number of elements to send
+    send_type: data type of elements being sent
+    recv_buff: receive output buffer
+    recv_count: number of elements to received
+    recv_type: data type of elements being received
+    comm: communicator
+
+ * Descrp: Function realizes the allgather operation using the recursive
+           doubling algorithm.
+
+ * Auther: MPICH / slightly modified by Ahmad Faraj.  
+
+ ****************************************************************************/
+int
+smpi_coll_tuned_alltoall_rdb(void * send_buff, int send_count, MPI_Datatype send_type,
+            void * recv_buff, int recv_count, MPI_Datatype recv_type,
+            MPI_Comm comm)
+{
+  /* MPI variables */
+  MPI_Status status;
+  MPI_Aint send_increment, recv_increment, extent;
+
+  int dst_tree_root, rank_tree_root, send_offset, recv_offset;
+  int rank, num_procs, j, k, dst, curr_size, max_size;
+  int last_recv_count, tmp_mask, tree_root, num_procs_completed;
+  int tag = 1, mask = 1, success = 1, failure = 0, c = 0, i = 0;
+
+  char * tmp_buff;
+  char * send_ptr = (char *) send_buff;
+  char * recv_ptr = (char *) recv_buff;
+
+  MPI_Comm_size(comm, &num_procs);
+  MPI_Comm_rank(comm, &rank);
+  MPI_Type_extent(send_type, &send_increment);
+  MPI_Type_extent(recv_type, &recv_increment);
+  MPI_Type_extent(recv_type, &extent);
+
+  send_increment *= (send_count * num_procs);
+  recv_increment *= (recv_count * num_procs);
+   
+  max_size = num_procs * recv_increment;
+  tmp_buff = (char * ) malloc(max_size);
+  if (!tmp_buff)
+    {
+      printf("alltoall-rdb:56: cannot allocate memory\n");
+      MPI_Finalize();
+      exit(failure);
+    }
+
+  curr_size = send_count * num_procs;
+
+  MPI_Sendrecv(send_ptr, curr_size, send_type, rank, tag,
+               tmp_buff + (rank * recv_increment),
+               curr_size, recv_type, rank, tag, comm, &status);
+
+  while (mask < num_procs)
+    {
+      dst = rank ^ mask;
+      dst_tree_root = dst >> i;
+      dst_tree_root <<= i;
+      rank_tree_root = rank >> i;
+      rank_tree_root <<= i;
+      send_offset = rank_tree_root * send_increment;
+      recv_offset = dst_tree_root * recv_increment;
+
+      if (dst < num_procs)
+       {
+         MPI_Sendrecv(tmp_buff + send_offset, curr_size, send_type, dst, tag,
+                       tmp_buff + recv_offset, mask * recv_count * num_procs,
+                       recv_type, dst, tag, comm, &status);
+
+         MPI_Get_count(&status, recv_type, &last_recv_count);
+         curr_size += last_recv_count;
+       }
+     
+     
+      if (dst_tree_root + mask > num_procs)
+       {
+
+         num_procs_completed = num_procs - rank_tree_root - mask;
+         /* num_procs_completed is the number of processes in this
+            subtree that have all the data. Send data to others
+            in a tree fashion. First find root of current tree
+            that is being divided into two. k is the number of
+            least-significant bits in this process's rank that
+            must be zeroed out to find the rank of the root */
+
+         j = mask;
+         k = 0;
+         while (j)
+           {
+             j >>= 1;
+             k++;
+           }
+         k--;
+
+         tmp_mask = mask >> 1;
+                  
+         while (tmp_mask)
+           {
+             dst = rank ^ tmp_mask;
+                      
+             tree_root = rank >> k;
+             tree_root <<= k;
+                      
+             /* send only if this proc has data and destination
+                doesn't have data. at any step, multiple processes
+                can send if they have the data */
+
+             if ((dst > rank)
+                 && (rank < tree_root + num_procs_completed)
+                 && (dst >= tree_root + num_procs_completed))
+               {
+                 MPI_Send(tmp_buff + dst_tree_root * send_increment,
+                           last_recv_count, send_type, dst, tag, comm);
+
+               }
+          
+             /* recv only if this proc. doesn't have data and sender
+                has data */
+                     
+             else if ((dst < rank)
+                      && (dst < tree_root + num_procs_completed)
+                      && (rank >= tree_root + num_procs_completed))
+               {
+                 MPI_Recv(tmp_buff + dst_tree_root * send_increment,
+                           mask * num_procs * send_count, send_type, dst,
+                           tag, comm, &status);
+
+                 MPI_Get_count(&status, send_type, &last_recv_count);
+                 curr_size += last_recv_count;
+               }
+
+             tmp_mask >>= 1;
+             k--;
+           }
+       }
+
+      mask <<= 1;
+      i++;
+    }
+
+  for (i = 0; i < num_procs; i++)
+     MPI_Sendrecv(tmp_buff + (rank + i * num_procs) * send_count * extent,
+                   send_count, send_type, rank, tag,
+                   recv_ptr + (i * recv_count * extent),
+                   recv_count, recv_type, rank, tag, comm, &status);
+  free(tmp_buff);
+  return success;
+}
diff --git a/src/smpi/colls/alltoall-ring-light-barrier.c b/src/smpi/colls/alltoall-ring-light-barrier.c
new file mode 100644 (file)
index 0000000..2508ed1
--- /dev/null
@@ -0,0 +1,72 @@
+#include "colls.h"
+/*****************************************************************************
+
+ * Function: alltoall_ring_light_barrier
+
+ * Return: int
+
+ * Inputs:
+    send_buff: send input buffer
+    send_count: number of elements to send
+    send_type: data type of elements being sent
+    recv_buff: receive output buffer
+    recv_count: number of elements to received
+    recv_type: data type of elements being received
+    comm: communicator
+
+ * Descrp: Function works in P - 1 steps. In step i, node j - i -> j -> j + i.
+           Light barriers are inserted between communications in different
+           phases.
+
+ * Auther: Ahmad Faraj
+
+ ****************************************************************************/
+int
+smpi_coll_tuned_alltoall_ring_light_barrier(void * send_buff, int send_count,
+                           MPI_Datatype send_type, void * recv_buff,
+                           int recv_count, MPI_Datatype recv_type,
+                           MPI_Comm comm)
+{
+  MPI_Aint send_chunk, recv_chunk;
+  MPI_Status s;
+  int i, src, dst, rank, num_procs, next_dst, next_src;
+  int tag = 1, success = 1; /*, failure = 0;*/
+
+  char send_sync = 'a', recv_sync = 'b';
+  char * send_ptr = (char *) send_buff;
+  char * recv_ptr = (char *) recv_buff;
+  
+  MPI_Comm_rank(comm, &rank);
+  MPI_Comm_size(comm, &num_procs);
+  MPI_Type_extent(send_type, &send_chunk);
+  MPI_Type_extent(recv_type, &recv_chunk);
+
+  send_chunk *= send_count;
+  recv_chunk *= recv_count;
+
+  MPI_Sendrecv(send_ptr + rank * send_chunk, send_count, send_type, rank, tag,
+              recv_ptr + rank * recv_chunk, recv_count, recv_type, rank, tag,
+              comm, &s);
+
+  for (i = 1; i < num_procs; i++)
+    {
+      src = (rank - i + num_procs) % num_procs;
+      dst = (rank + i) % num_procs;
+      
+      MPI_Sendrecv(send_ptr + dst * send_chunk, send_count, send_type,
+                  dst, tag, recv_ptr + src * recv_chunk, recv_count,
+                  recv_type, src, tag, comm, &s);
+
+      if ((i + 1) < num_procs)
+       {
+         next_src = (rank - (i + 1) + num_procs) % num_procs;
+         next_dst = (rank + (i + 1) + num_procs) % num_procs;
+         MPI_Sendrecv(&send_sync, 1, MPI_CHAR, next_src, tag,
+                      &recv_sync, 1, MPI_CHAR, next_dst, tag,
+                      comm, &s);
+         
+       }
+    }
+
+  return success;
+}
diff --git a/src/smpi/colls/alltoall-ring-mpi-barrier.c b/src/smpi/colls/alltoall-ring-mpi-barrier.c
new file mode 100644 (file)
index 0000000..c5621b3
--- /dev/null
@@ -0,0 +1,57 @@
+#include "colls.h"
+/*****************************************************************************
+
+ * Function: alltoall_ring_mpi_barrier
+
+ * Return: int
+
+ * Inputs:
+    send_buff: send input buffer
+    send_count: number of elements to send
+    send_type: data type of elements being sent
+    recv_buff: receive output buffer
+    recv_count: number of elements to received
+    recv_type: data type of elements being received
+    comm: communicator
+
+ * Descrp: Function works in P - 1 steps. In step i, node j - i -> j -> j + i.
+           MPI barriers are added between each two phases.
+
+ * Auther: Ahmad Faraj
+
+ ****************************************************************************/
+int
+smpi_coll_tuned_alltoall_ring_mpi_barrier(void * send_buff, int send_count,
+                           MPI_Datatype send_type, void * recv_buff,
+                           int recv_count, MPI_Datatype recv_type,
+                           MPI_Comm comm)
+{
+  MPI_Status s;
+  MPI_Aint send_chunk, recv_chunk;
+  int i, src, dst, rank, num_procs;
+  int tag = 1, success = 1; /*, failure = 0, pof2 = 1;*/
+
+  char * send_ptr = (char *) send_buff;
+  char * recv_ptr = (char *) recv_buff;
+  
+  MPI_Comm_rank(comm, &rank);
+  MPI_Comm_size(comm, &num_procs);
+  MPI_Type_extent(send_type, &send_chunk);
+  MPI_Type_extent(recv_type, &recv_chunk);
+
+  send_chunk *= send_count;
+  recv_chunk *= recv_count;  
+
+  for (i = 0; i < num_procs; i++)
+    {
+      src = (rank - i + num_procs) % num_procs;
+      dst = (rank + i) % num_procs;
+      
+      MPI_Barrier(comm);
+      MPI_Sendrecv(send_ptr + dst * send_chunk, send_count, send_type, dst,
+                  tag, recv_ptr + src * recv_chunk, recv_count, recv_type,
+                  src, tag, comm, &s);
+    }
+
+  return success;
+}
diff --git a/src/smpi/colls/alltoall-ring-one-barrier.c b/src/smpi/colls/alltoall-ring-one-barrier.c
new file mode 100644 (file)
index 0000000..13bedcb
--- /dev/null
@@ -0,0 +1,54 @@
+#include "colls.h"
+/*****************************************************************************
+
+ * Function: alltoall_ring
+
+ * Return: int
+
+ * Inputs:
+    send_buff: send input buffer
+    send_count: number of elements to send
+    send_type: data type of elements being sent
+    recv_buff: receive output buffer
+    recv_count: number of elements to received
+    recv_type: data type of elements being received
+    comm: communicator
+
+ * Descrp: Function works in P - 1 steps. In step i, node j - i -> j -> j + i.
+
+ * Auther: Ahmad Faraj
+
+ ****************************************************************************/
+int
+smpi_coll_tuned_alltoall_ring_one_barrier(void * send_buff, int send_count, MPI_Datatype send_type,
+                         void * recv_buff, int recv_count, MPI_Datatype recv_type,
+                         MPI_Comm comm)
+{
+  MPI_Status s;
+  MPI_Aint send_chunk, recv_chunk;
+  int i, src, dst, rank, num_procs;
+  int tag = 1, success = 1; /*, failure = 0, pof2 = 1; */
+
+  char * send_ptr = (char *) send_buff;
+  char * recv_ptr = (char *) recv_buff;
+  
+  MPI_Comm_rank(comm, &rank);
+  MPI_Comm_size(comm, &num_procs);
+  MPI_Type_extent(send_type, &send_chunk);
+  MPI_Type_extent(recv_type, &recv_chunk);
+
+  send_chunk *= send_count;
+  recv_chunk *= recv_count;  
+
+  MPI_Barrier(comm);
+  for (i = 0; i < num_procs; i++)
+    {
+      src = (rank - i + num_procs) % num_procs;
+      dst = (rank + i) % num_procs;
+      
+      MPI_Sendrecv(send_ptr + dst * send_chunk, send_count, send_type, dst,
+                  tag, recv_ptr + src * recv_chunk, recv_count, recv_type,
+                  src, tag, comm, &s);
+    }
+  return success;
+}
diff --git a/src/smpi/colls/alltoall-ring.c b/src/smpi/colls/alltoall-ring.c
new file mode 100644 (file)
index 0000000..e5e4e2b
--- /dev/null
@@ -0,0 +1,53 @@
+#include "colls.h"
+/*****************************************************************************
+
+ * Function: alltoall_ring
+
+ * Return: int
+
+ * Inputs:
+    send_buff: send input buffer
+    send_count: number of elements to send
+    send_type: data type of elements being sent
+    recv_buff: receive output buffer
+    recv_count: number of elements to received
+    recv_type: data type of elements being received
+    comm: communicator
+
+ * Descrp: Function works in P - 1 steps. In step i, node j - i -> j -> j + i.
+
+ * Auther: Ahmad Faraj
+
+ ****************************************************************************/
+int
+smpi_coll_tuned_alltoall_ring(void * send_buff, int send_count, MPI_Datatype send_type,
+             void * recv_buff, int recv_count, MPI_Datatype recv_type,
+             MPI_Comm comm)
+{
+  MPI_Status s;
+  MPI_Aint send_chunk, recv_chunk;
+  int i, src, dst, rank, num_procs;
+  int tag = 1, success = 1; /*, failure = 0, pof2 = 1*/;
+
+  char * send_ptr = (char *) send_buff;
+  char * recv_ptr = (char *) recv_buff;
+  
+  MPI_Comm_rank(comm, &rank);
+  MPI_Comm_size(comm, &num_procs);
+  MPI_Type_extent(send_type, &send_chunk);
+  MPI_Type_extent(recv_type, &recv_chunk);
+
+  send_chunk *= send_count;
+  recv_chunk *= recv_count;  
+
+  for (i = 0; i < num_procs; i++)
+    {
+      src = (rank - i + num_procs) % num_procs;
+      dst = (rank + i) % num_procs;
+      
+      MPI_Sendrecv(send_ptr + dst * send_chunk, send_count, send_type, dst,
+                  tag, recv_ptr + src * recv_chunk, recv_count, recv_type,
+                  src, tag, comm, &s);
+    }
+  return success;
+}
diff --git a/src/smpi/colls/alltoall-simple.c b/src/smpi/colls/alltoall-simple.c
new file mode 100644 (file)
index 0000000..df2be4e
--- /dev/null
@@ -0,0 +1,126 @@
+#include "colls.h"
+
+/*****************************************************************************
+
+ * Function: alltoall_spreading_simple
+
+ * Return: int
+
+ *  Inputs:
+    send_buff: send input buffer
+    send_count: number of elements to send
+    send_type: data type of elements being sent
+    recv_buff: receive output buffer
+    recv_count: number of elements to received
+    recv_type: data type of elements being received
+    comm: communicator
+
+ * Descrp: Let i -> j denote the communication from node i to node j. The
+          order of communications for node i is i -> i + 1, i -> i + 2, ...,
+          i -> (i + p -1) % P.
+ * Auther: Ahmad Faraj
+
+ ****************************************************************************/
+int
+smpi_coll_tuned_alltoall_simple(void * send_buff, int send_count,
+               MPI_Datatype send_type, void * recv_buff,
+               int recv_count, MPI_Datatype recv_type,
+               MPI_Comm comm)
+{
+  int i, rank, size, nreqs, err, src, dst, tag = 101;
+  char *psnd;
+  char *prcv;
+  MPI_Aint sndinc;
+  MPI_Aint rcvinc;
+  MPI_Request *req;
+  MPI_Request *preq;
+  MPI_Request *qreq;
+  MPI_Status s, * statuses;
+
+
+  MPI_Comm_size(comm, &size);
+  MPI_Comm_rank(comm, &rank);
+  MPI_Type_extent(send_type, &sndinc);
+  MPI_Type_extent(recv_type, &rcvinc);
+  sndinc *= send_count;
+  rcvinc *= recv_count;
+
+  /* Allocate arrays of requests. */
+
+  nreqs = 2 * (size - 1);
+  if (nreqs > 0)
+    {
+      req = (MPI_Request *) malloc(nreqs * sizeof(MPI_Request));
+      statuses = (MPI_Status *) malloc(nreqs * sizeof(MPI_Status));
+      if (!req || !statuses)
+       {
+         free(req);
+         free(statuses);
+         return 0;
+       }
+    }
+  else
+    req = 0;
+
+  /* simple optimization */
+
+  psnd = ((char *) send_buff) + (rank * sndinc);
+  prcv = ((char *) recv_buff) + (rank * rcvinc);
+  MPI_Sendrecv (psnd, send_count, send_type, rank, tag,
+               prcv, recv_count, recv_type,
+               rank, tag, comm, &s);
+
+
+  /* Initiate all send/recv to/from others. */
+
+  preq = req;
+  qreq = req + size - 1;
+  prcv = (char*) recv_buff;
+  psnd = (char*) send_buff;
+  for (i = 0; i < size; i++)
+    {
+      src = dst = (rank + i) % size;
+      if (src == rank) continue;
+      if (dst == rank) continue;      
+      MPI_Recv_init(prcv + (src * rcvinc), recv_count, recv_type, src,
+                   tag, comm, preq++);
+      MPI_Send_init(psnd + (dst * sndinc), send_count, send_type, dst,
+                   tag, comm, qreq++);
+    }
+
+  /* Start all the requests. */
+
+  err = MPI_Startall(nreqs, req);
+
+  /* Wait for them all. */
+
+  err = MPI_Waitall(nreqs, req, statuses);
+
+  if (err != MPI_SUCCESS) {
+    if (req)
+      free((char *) req);
+    return err;
+  }
+
+  for (i = 0, preq = req; i < nreqs; ++i, ++preq) {
+    err = MPI_Request_free(preq);
+    if (err != MPI_SUCCESS) {
+      if (req)
+       free((char *) req);
+      if (statuses)
+       free(statuses);
+      return err;
+    }
+  }
+
+  /* All done */
+
+  if (req)
+    free((char *) req);
+  if (statuses)
+    free(statuses);
+  return (1);
+}
+
+
diff --git a/src/smpi/colls/colls.h b/src/smpi/colls/colls.h
new file mode 100644 (file)
index 0000000..15d28ff
--- /dev/null
@@ -0,0 +1,66 @@
+#ifndef SMPI_COLLS_H
+#define SMPI_COLLS_H
+
+#include "smpi/mpi.h"
+#include "xbt.h"
+
+int smpi_coll_tuned_alltoall_2dmesh(
+  void * send_buff, int send_count, MPI_Datatype send_type,
+  void * recv_buff, int recv_count, MPI_Datatype recv_type,
+  MPI_Comm comm);
+int smpi_coll_tuned_alltoall_3dmesh(
+  void * send_buff, int send_count, MPI_Datatype send_type,
+  void * recv_buff, int recv_count, MPI_Datatype recv_type,
+  MPI_Comm comm);
+/*int smpi_coll_tuned_alltoall_bruck(
+  void * send_buff, int send_count, MPI_Datatype send_type,
+  void * recv_buff, int recv_count, MPI_Datatype recv_type,
+  MPI_Comm comm);*/
+int smpi_coll_tuned_alltoall_pair(
+  void * send_buff, int send_count, MPI_Datatype send_type,
+  void * recv_buff, int recv_count, MPI_Datatype recv_type,
+  MPI_Comm comm);
+int smpi_coll_tuned_alltoall_pair_light_barrier(
+  void * send_buff, int send_count, MPI_Datatype send_type,
+  void * recv_buff, int recv_count, MPI_Datatype recv_type,
+  MPI_Comm comm);
+int smpi_coll_tuned_alltoall_pair_mpi_barrier(
+  void * send_buff, int send_count, MPI_Datatype send_type,
+  void * recv_buff, int recv_count, MPI_Datatype recv_type,
+  MPI_Comm comm);
+int smpi_coll_tuned_alltoall_pair_one_barrier(
+  void * send_buff, int send_count, MPI_Datatype send_type,
+  void * recv_buff, int recv_count, MPI_Datatype recv_type,
+  MPI_Comm comm);
+int smpi_coll_tuned_alltoall_rdb(
+  void * send_buff, int send_count, MPI_Datatype send_type,
+  void * recv_buff, int recv_count, MPI_Datatype recv_type,
+  MPI_Comm comm);
+int smpi_coll_tuned_alltoall_ring(
+  void * send_buff, int send_count, MPI_Datatype send_type,
+  void * recv_buff, int recv_count, MPI_Datatype recv_type,
+  MPI_Comm comm);
+int smpi_coll_tuned_alltoall_ring_light_barrier(
+  void * send_buff, int send_count, MPI_Datatype send_type,
+  void * recv_buff, int recv_count, MPI_Datatype recv_type,
+  MPI_Comm comm);
+int smpi_coll_tuned_alltoall_ring_mpi_barrier(
+  void * send_buff, int send_count, MPI_Datatype send_type,
+  void * recv_buff, int recv_count, MPI_Datatype recv_type,
+  MPI_Comm comm);
+int smpi_coll_tuned_alltoall_ring_one_barrier(
+  void * send_buff, int send_count, MPI_Datatype send_type,
+  void * recv_buff, int recv_count, MPI_Datatype recv_type,
+  MPI_Comm comm);
+int smpi_coll_tuned_alltoall_simple(
+  void * send_buff, int send_count, MPI_Datatype send_type,
+  void * recv_buff, int recv_count, MPI_Datatype recv_type,
+  MPI_Comm comm);
+
+
+int smpi_coll_tuned_allgather_2dmesh(
+  void * send_buff, int send_count, MPI_Datatype send_type,
+  void * recv_buff, int recv_count, MPI_Datatype recv_type,
+  MPI_Comm comm);
+
+#endif
index d5b577c..43f8c36 100644 (file)
@@ -239,6 +239,10 @@ void nary_tree_bcast(void *buf, int count, MPI_Datatype datatype, int root,
                      MPI_Comm comm, int arity);
 void nary_tree_barrier(MPI_Comm comm, int arity);
 
+int smpi_coll_tuned_alltoall_ompi(void *sendbuf, int sendcount,
+                                      MPI_Datatype sendtype, void *recvbuf,
+                                      int recvcount, MPI_Datatype recvtype,
+                                      MPI_Comm comm);
 int smpi_coll_tuned_alltoall_bruck(void *sendbuf, int sendcount,
                                    MPI_Datatype sendtype, void *recvbuf,
                                    int recvcount, MPI_Datatype recvtype,
index 7798de8..af699b9 100644 (file)
 #include <assert.h>
 
 #include "private.h"
+#include "colls/colls.h"
+
+s_mpi_coll_description_t mpi_coll_alltoall_description[] = {
+  {"ompi",
+   "Ompi alltoall default collective",
+   smpi_coll_tuned_alltoall_ompi},
+
+  {"2dmesh",
+   "Alltoall 2dmesh collective",
+   smpi_coll_tuned_alltoall_2dmesh},
+  {"3dmesh",
+   "Alltoall 3dmesh collective",
+   smpi_coll_tuned_alltoall_3dmesh},
+  /*{"bruck",
+   "Alltoall Bruck collective",
+   smpi_coll_tuned_alltoall_bruck},*/
+  {"pair",
+   "Alltoall pair collective",
+   smpi_coll_tuned_alltoall_pair},
+  {"pair_light_barrier",
+   "Alltoall pair_light_barrier collective",
+   smpi_coll_tuned_alltoall_pair_light_barrier},
+  {"pair_mpi_barrier",
+   "Alltoall pair_mpi_barrier collective",
+   smpi_coll_tuned_alltoall_pair_mpi_barrier},
+  {"rdb",
+   "Alltoall rdb collective",
+   smpi_coll_tuned_alltoall_rdb},
+  {"ring",
+   "Alltoall ring collective",
+   smpi_coll_tuned_alltoall_ring},
+  {"ring_light_barrier",
+   "Alltoall ring_light_barrier collective",
+   smpi_coll_tuned_alltoall_ring_light_barrier},
+  {"ring_light_barrier",
+   "Alltoall ring_light_barrier collective",
+   smpi_coll_tuned_alltoall_ring_light_barrier},
+  {"ring_mpi_barrier",
+   "Alltoall ring_mpi_barrier collective",
+   smpi_coll_tuned_alltoall_ring_mpi_barrier},
+  {"ring_one_barrier",
+   "Alltoall ring_one_barrier collective",
+   smpi_coll_tuned_alltoall_ring_one_barrier},
+  {"simple",
+   "Alltoall simple collective",
+   smpi_coll_tuned_alltoall_simple},
+
+  {"bruck",
+   "Alltoall Bruck (SG) collective",
+   smpi_coll_tuned_alltoall_bruck},
+  {"basic_linear",
+   "Alltoall basic linear (SG) collective",
+   smpi_coll_tuned_alltoall_basic_linear},
+  {"pairwise",
+   "Alltoall pairwise (SG) collective",
+   smpi_coll_tuned_alltoall_pairwise},
+
+  {NULL, NULL, NULL}      /* this array must be NULL terminated */
+};
+
+s_mpi_coll_description_t mpi_coll_allgather_description[] = {
+  {"default",
+   "allgather default collective",
+   smpi_mpi_gather},
+
+  {NULL, NULL, NULL}      /* this array must be NULL terminated */
+};
+
+
+/** Displays the long description of all registered models, and quit */
+void coll_help(const char *category, s_mpi_coll_description_t * table)
+{
+  int i;
+  printf("Long description of the %s models accepted by this simulator:\n",
+         category);
+  for (i = 0; table[i].name; i++)
+    printf("  %s: %s\n", table[i].name, table[i].description);
+}
+
+int find_coll_description(s_mpi_coll_description_t * table,
+                           const char *name)
+{
+  int i;
+  char *name_list = NULL;
+
+  for (i = 0; table[i].name; i++)
+    if (!strcmp(name, table[i].name)) {
+      return i;
+    }
+  name_list = strdup(table[0].name);
+  for (i = 1; table[i].name; i++) {
+    name_list =
+        xbt_realloc(name_list,
+                    strlen(name_list) + strlen(table[i].name) + 3);
+    strcat(name_list, ", ");
+    strcat(name_list, table[i].name);
+  }
+  xbt_die("Model '%s' is invalid! Valid models are: %s.", name, name_list);
+  return -1;
+}
+
+
 
 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(smpi_coll, smpi,
                                 "Logging specific to SMPI (coll)");
@@ -192,6 +294,32 @@ void nary_tree_barrier(MPI_Comm comm, int arity)
   free_tree(tree);
 }
 
+int smpi_coll_tuned_alltoall_ompi(void *sendbuf, int sendcount,
+                                   MPI_Datatype sendtype, void *recvbuf,
+                                   int recvcount, MPI_Datatype recvtype,
+                                   MPI_Comm comm)
+{
+  int size, sendsize;  
+  size = smpi_comm_size(comm); 
+  sendsize = smpi_datatype_size(sendtype) * sendcount; 
+  if (sendsize < 200 && size > 12) {
+    return
+        smpi_coll_tuned_alltoall_bruck(sendbuf, sendcount, sendtype,
+                                       recvbuf, recvcount, recvtype,
+                                       comm);
+  } else if (sendsize < 3000) {
+    return
+        smpi_coll_tuned_alltoall_basic_linear(sendbuf, sendcount,
+                                              sendtype, recvbuf,
+                                              recvcount, recvtype, comm);
+  } else {
+    return
+        smpi_coll_tuned_alltoall_pairwise(sendbuf, sendcount, sendtype,
+                                          recvbuf, recvcount, recvtype,
+                                          comm);
+  }
+}
+
 /**
  * Alltoall Bruck
  *
@@ -261,7 +389,7 @@ int smpi_coll_tuned_alltoall_bruck(void *sendbuf, int sendcount,
 }
 
 /**
- * Alltoall basic_linear
+ * Alltoall basic_linear (STARMPI:alltoall-simple)
  **/
 int smpi_coll_tuned_alltoall_basic_linear(void *sendbuf, int sendcount,
                                           MPI_Datatype sendtype,
index 46f1abd..002ece0 100644 (file)
@@ -13,6 +13,18 @@ XBT_LOG_NEW_DEFAULT_SUBCATEGORY(smpi_mpi, smpi,
 
 int MPI_Init(int *argc, char ***argv)
 {
+  int alltoall_id = find_coll_description(mpi_coll_alltoall_description,
+                                          sg_cfg_get_string("smpi/alltoall"));
+  mpi_coll_alltoall_fun = (int (*)(void *, int, MPI_Datatype,
+                                  void*, int, MPI_Datatype, MPI_Comm))
+                         mpi_coll_alltoall_description[alltoall_id].coll;
+
+  int allgather_id = find_coll_description(mpi_coll_allgather_description,
+                                           sg_cfg_get_string("smpi/allgather"));
+  mpi_coll_allgather_fun = (int (*)(void *, int, MPI_Datatype,
+                                   void*, int, MPI_Datatype, MPI_Comm))
+                          mpi_coll_allgather_description[allgather_id].coll;
+
   return PMPI_Init(argc, argv);
 }
 
index 3707670..58cfb15 100644 (file)
@@ -1917,7 +1917,7 @@ int PMPI_Alltoall(void *sendbuf, int sendcount, MPI_Datatype sendtype,
                  void *recvbuf, int recvcount, MPI_Datatype recvtype,
                  MPI_Comm comm)
 {
-  int retval, size, sendsize;
+  int retval;
 
   smpi_bench_end();
 #ifdef HAVE_TRACING
@@ -1931,24 +1931,7 @@ int PMPI_Alltoall(void *sendbuf, int sendcount, MPI_Datatype sendtype,
              || recvtype == MPI_DATATYPE_NULL) {
     retval = MPI_ERR_TYPE;
   } else {
-    size = smpi_comm_size(comm);
-    sendsize = smpi_datatype_size(sendtype) * sendcount;
-    if (sendsize < 200 && size > 12) {
-      retval =
-          smpi_coll_tuned_alltoall_bruck(sendbuf, sendcount, sendtype,
-                                         recvbuf, recvcount, recvtype,
-                                         comm);
-    } else if (sendsize < 3000) {
-      retval =
-          smpi_coll_tuned_alltoall_basic_linear(sendbuf, sendcount,
-                                                sendtype, recvbuf,
-                                                recvcount, recvtype, comm);
-    } else {
-      retval =
-          smpi_coll_tuned_alltoall_pairwise(sendbuf, sendcount, sendtype,
-                                            recvbuf, recvcount, recvtype,
-                                            comm);
-    }
+    retval = mpi_coll_alltoall_fun(sendbuf, sendcount, sendtype, recvbuf, recvcount, recvtype, comm);
   }
 #ifdef HAVE_TRACING
   TRACE_smpi_collective_out(rank, -1, __FUNCTION__);
index b09c634..0a13e38 100644 (file)
@@ -147,7 +147,7 @@ typedef union YYSTYPE
   double real;
   int integer;
   char* string;
-  xbt_exp_label_t label;
+  xbt_automaton_exp_label_t label;
 
 
 
index 61d7da7..bede162 100644 (file)
@@ -534,7 +534,7 @@ int compare_area(void *area1, void* area2, xbt_dynar_t previous){ /* Return code
   size_t i = 0, pointer_align = 0, ignore1 = 0, ignore2 = 0;
   void *addr_pointed1, *addr_pointed2;
   int res_compare;
-  size_t block1, frag1, block2, frag2;
+  ssize_t block1, frag1, block2, frag2;
   ssize_t size;
   int check_ignore = 0;
   int j;
@@ -595,18 +595,21 @@ int compare_area(void *area1, void* area2, xbt_dynar_t previous){ /* Return code
           return 1;
         }
       }
+
       if(heapinfo1[block1].busy_block.size != heapinfo2[block2].busy_block.size){
         if(match_pairs){
           xbt_dynar_free(&previous);
         }
         return 1;
       }
+
       if(heapinfo1[block1].busy_block.busy_size != heapinfo2[block2].busy_block.busy_size){
         if(match_pairs){
           xbt_dynar_free(&previous);
         }
         return 2;
       }
+
       if(!add_heap_area_pair(previous, block1, -1, block2, -1)){
         if(match_pairs){
           match_equals(previous);
@@ -616,13 +619,22 @@ int compare_area(void *area1, void* area2, xbt_dynar_t previous){ /* Return code
       }
  
       size = heapinfo1[block1].busy_block.busy_size;
+
+      if(size <= 0){
+        if(match_pairs){
+          match_equals(previous);
+          xbt_dynar_free(&previous);
+        }
+        return 0;
+      }
+
       frag1 = -1;
       frag2 = -1;
 
       area1_to_compare = addr_block1;
       area2_to_compare = addr_block2;
 
-      if(heapinfo1[block1].busy_block.ignore == 1 || heapinfo2[block2].busy_block.ignore == 1)
+      if(heapinfo1[block1].busy_block.ignore == 1 && heapinfo2[block2].busy_block.ignore == 1)
         check_ignore = 1;
       
     }else{
@@ -667,7 +679,7 @@ int compare_area(void *area1, void* area2, xbt_dynar_t previous){ /* Return code
 
       size = heapinfo1[block1].busy_frag.frag_size[frag1];
 
-      if(size == -1){
+      if(size <= 0){
         if(match_pairs){
           match_equals(previous);
           xbt_dynar_free(&previous);
@@ -675,10 +687,11 @@ int compare_area(void *area1, void* area2, xbt_dynar_t previous){ /* Return code
         return 0;
       }
       
-      if(heapinfo1[block1].busy_frag.ignore[frag1] == 1 || heapinfo2[block2].busy_frag.ignore[frag2] == 1)
+      if(heapinfo1[block1].busy_frag.ignore[frag1] == 1 && heapinfo2[block2].busy_frag.ignore[frag2] == 1)
         check_ignore = 1;
       
     }
+
   }else if((heapinfo1[block1].type > 0) && (heapinfo2[block2].type > 0)){
 
     frag1 = ((uintptr_t) (ADDR2UINT (area1) % (BLOCKSIZE))) >> heapinfo1[block1].type;
@@ -722,14 +735,15 @@ int compare_area(void *area1, void* area2, xbt_dynar_t previous){ /* Return code
       
     size = heapinfo1[block1].busy_frag.frag_size[frag1];
 
-    if(size == -1){
+    if(size <= 0){
       if(match_pairs){
+        match_equals(previous);
         xbt_dynar_free(&previous);
       }
       return 0;
     }
 
-    if(heapinfo1[block1].busy_frag.ignore[frag1] == 1 || heapinfo2[block2].busy_frag.ignore[frag2] == 1)
+    if(heapinfo1[block1].busy_frag.ignore[frag1] == 1 && heapinfo2[block2].busy_frag.ignore[frag2] == 1)
       check_ignore = 1;   
     
   }else{
@@ -760,13 +774,19 @@ int compare_area(void *area1, void* area2, xbt_dynar_t previous){ /* Return code
     }else if((addr_pointed1 > s_heap) && ((char *)addr_pointed1 < (char *)s_heap + STD_HEAP_SIZE) 
            && (addr_pointed2 > s_heap) && ((char *)addr_pointed2 < (char *)s_heap + STD_HEAP_SIZE)){
       res_compare = compare_area(addr_pointed1, addr_pointed2, previous);
-      if(res_compare != 0)
+      if(res_compare != 0){
+        if(match_pairs)
+          xbt_dynar_free(&previous);
         return res_compare;
+      }
     }else{
       j=0;
       while(j<sizeof(void*) && (i + j) < size){
-        if(memcmp(((char *)area1_to_compare) + i + j, ((char *)area2_to_compare) + i + j , 1) != 0)
+        if(memcmp(((char *)area1_to_compare) + i + j, ((char *)area2_to_compare) + i + j , 1) != 0){
+          if(match_pairs)
+            xbt_dynar_free(&previous);
           return 1;
+        }
         j++;
       }
     }
@@ -776,6 +796,7 @@ int compare_area(void *area1, void* area2, xbt_dynar_t previous){ /* Return code
 
   if(match_pairs){
     match_equals(previous);
+    xbt_dynar_free(&previous);
   }
 
   return 0;