updated binary_tree

tsung-wei-huang · tsung-wei-huang · commit 9d4bcb1989b3 · 2019-06-17T15:16:03.000-05:00
diff --git a/CMakeLists.txt b/CMakeLists.txt
@@ -273,6 +273,7 @@ add_executable(
   binary_tree 
   ${TF_BENCHMARK_DIR}/binary_tree/main.cpp
   ${TF_BENCHMARK_DIR}/binary_tree/tbb.cpp
+  ${TF_BENCHMARK_DIR}/binary_tree/omp.cpp
   ${TF_BENCHMARK_DIR}/binary_tree/taskflow.cpp
 )
 target_include_directories(binary_tree PRIVATE ${PROJECT_SOURCE_DIR}/3rd-party/CLI11)
diff --git a/benchmark/binary_tree/binary_tree.hpp b/benchmark/binary_tree/binary_tree.hpp
@@ -9,6 +9,7 @@
 #include <cmath>
 #include <atomic>
 
-std::chrono::microseconds measure_time_taskflow(unsigned, unsigned);
-std::chrono::microseconds measure_time_tbb(unsigned, unsigned);
+std::chrono::microseconds measure_time_taskflow(size_t, unsigned);
+std::chrono::microseconds measure_time_tbb(size_t, unsigned);
+std::chrono::microseconds measure_time_omp(size_t, unsigned);
 
diff --git a/benchmark/binary_tree/main.cpp b/benchmark/binary_tree/main.cpp
@@ -3,6 +3,7 @@
 
 void binary_tree(
   const std::string& model,
+  const size_t num_layers,
   const unsigned num_threads, 
   const unsigned num_rounds
   ) {
@@ -11,7 +12,7 @@ void binary_tree(
             << std::setw(12) << "runtime"
             << std::endl;
   
-  for(unsigned i=1; i<=21; ++i) {
+  for(size_t i=1; i<=num_layers; ++i) {
 
     double runtime {0.0};
 
@@ -22,6 +23,9 @@ void binary_tree(
       else if(model == "tbb") {
         runtime += measure_time_tbb(i, num_threads).count();
       }
+      else if(model == "omp") {
+        runtime += measure_time_omp(i, num_threads).count();
+      }
       else assert(false);
     }
 
@@ -40,12 +44,15 @@ int main(int argc, char* argv[]) {
 
   unsigned num_rounds {1};  
   app.add_option("-r,--num_rounds", num_rounds, "number of rounds (default=1)");
+  
+  size_t num_layers {25};  
+  app.add_option("-l,--num_layers", num_layers, "number of layers (default=25)");
 
   std::string model = "tf";
   app.add_option("-m,--model", model, "model name tbb|omp|tf (default=tf)")
      ->check([] (const std::string& m) {
-        if(m != "tbb" && m != "tf") {
-          return "model name should be \"tbb\" or \"tf\"";
+        if(m != "tbb" && m != "tf" && m != "omp") {
+          return "model name should be \"tbb\", \"omp\", or \"tf\"";
         }
         return "";
      });
@@ -57,7 +64,7 @@ int main(int argc, char* argv[]) {
             << "num_rounds=" << num_rounds << ' '
             << std::endl;
 
-  binary_tree(model, num_threads, num_rounds);
+  binary_tree(model, num_layers, num_threads, num_rounds);
 
   return 0;
 }
diff --git a/benchmark/binary_tree/omp.cpp b/benchmark/binary_tree/omp.cpp
@@ -0,0 +1,55 @@
+#include "binary_tree.hpp"
+#include <omp.h>
+
+// binary_tree_omp
+void binary_tree_omp(size_t num_layers, unsigned num_threads) {
+
+  std::atomic<size_t> counter = 0;
+  
+  size_t N = 1 << num_layers;
+  size_t *D = new size_t [N]; 
+
+  #pragma omp parallel num_threads(num_threads)
+  {
+    #pragma omp single
+    {
+      for(size_t i = 1; i<N; ++i) {
+        
+        size_t p = i / 2;
+        size_t l = i * 2;
+        size_t r = l + 1;
+        
+        if(l < N && r < N) {
+          #pragma omp task firstprivate(i) depend(out:D[l], D[r]) depend(in:D[p])
+          {
+            //printf("%d\n", i);
+            counter.fetch_add(1, std::memory_order_relaxed);
+          }
+        }
+        else {
+          #pragma omp task firstprivate(i) depend(in:D[p])
+          {
+            //printf("%d\n", i);
+            counter.fetch_add(1, std::memory_order_relaxed);
+          }
+        }
+      }
+    }
+  }
+
+  assert((counter + 1) == N);
+
+  delete [] D;
+}
+
+std::chrono::microseconds measure_time_omp(
+  size_t num_layers,
+  unsigned num_threads
+) {
+  auto beg = std::chrono::high_resolution_clock::now();
+  binary_tree_omp(num_layers, num_threads);
+  auto end = std::chrono::high_resolution_clock::now();
+  return std::chrono::duration_cast<std::chrono::microseconds>(end - beg);
+}
+
+
diff --git a/benchmark/binary_tree/taskflow.cpp b/benchmark/binary_tree/taskflow.cpp
@@ -2,7 +2,7 @@
 #include <taskflow/taskflow.hpp> 
 
 // binary_tree_taskflow
-void binary_tree_taskflow(unsigned num_layers, unsigned num_threads) {
+void binary_tree_taskflow(size_t num_layers, unsigned num_threads) {
 
   std::atomic<size_t> counter {0};
 
@@ -30,7 +30,7 @@ void binary_tree_taskflow(unsigned num_layers, unsigned num_threads) {
 }
 
 std::chrono::microseconds measure_time_taskflow(
-  unsigned num_layers,
+  size_t num_layers,
   unsigned num_threads
 ) {
   auto beg = std::chrono::high_resolution_clock::now();
diff --git a/benchmark/binary_tree/tbb.cpp b/benchmark/binary_tree/tbb.cpp
@@ -3,7 +3,7 @@
 #include <tbb/flow_graph.h>
 
 // binary_tree_tbb
-void binary_tree_tbb(unsigned num_layers, unsigned num_threads) {
+void binary_tree_tbb(size_t num_layers, unsigned num_threads) {
 
   using namespace tbb;
   using namespace tbb::flow;
@@ -44,7 +44,7 @@ void binary_tree_tbb(unsigned num_layers, unsigned num_threads) {
 }
 
 std::chrono::microseconds measure_time_tbb(
-  unsigned num_layers,
+  size_t num_layers,
   unsigned num_threads
 ) {
   auto beg = std::chrono::high_resolution_clock::now();

Original file line number	Diff line number	Diff line change
`@@ -273,6 +273,7 @@ add_executable(`
`273`	`273`	`binary_tree`
`274`	`274`	`${TF_BENCHMARK_DIR}/binary_tree/main.cpp`
`275`	`275`	`${TF_BENCHMARK_DIR}/binary_tree/tbb.cpp`
	`276`	`+ ${TF_BENCHMARK_DIR}/binary_tree/omp.cpp`
`276`	`277`	`${TF_BENCHMARK_DIR}/binary_tree/taskflow.cpp`
`277`	`278`	`)`
`278`	`279`	`target_include_directories(binary_tree PRIVATE ${PROJECT_SOURCE_DIR}/3rd-party/CLI11)`