Parallel Algorithms: Difference between revisions

← Older edit Newer edit →

@@ Line 704: / Line 704: @@
 The benefit of this segmented compaction/prefix sum is that if you only do each segment once in an iterative algorithm such as parallel BFS,
 you can get <math>O(n^2)</math> or <math>O(m)</math> work.
+==XMT Programming Tips==
+I never figured out how to use standard c headers.
+XMT only has int (32 bit) and float (32 bit). If you need a bool type, you will need to define it in a header.
+Here is my helpers header <code>helpers.h</code>
+{{ hidden | <code>helpers.h</code> |
+<syntaxhighlight lang="c">
+#ifndef HELPERS_H
+#define HELPERS_H
+#define true 1
+#define false 0
+#define bool int
+int max(int a, int b) {
+  return a < b ? b : a;
+}
+int min(int a, int b) {
+  return a < b ? a : b;
+}
+#endif
+</syntaxhighlight>
+}}
+If you prefer to debug in C++ like me, you can use the following code to adapt running the XMT code:
+This code does not run things asynchronously.
+{{hidden | C++ Code |
+<syntaxhighlight lang="cpp">
+#define spawn(x, y) for (int $ = x; $ <= y; ++$)
+//#define spawn(x, y) for (int $ = y; $ >= x; --$)
+#define ps(a, b) \
+  {              \
+    b += a;      \
+    a = b - a;   \
+  }
+#define psm(a, b) \
+  {               \
+    b += a;       \
+    a = b - a;    \
+  }
+#define psBaseReg int
+int main() {
+  vertices.resize(N);
+  degrees.resize(N);
+  edges = std::vector<std::vector<int>>(M, std::vector<int>(2));
+  antiparallel.resize(M);
+  bcc.resize(M);
+  string datapath = "data/" STRINGIFY(GRAPH_NUM) "/graph.txt";
+  string data = readFile(datapath);
+  regex section_regex(
+      "[\\n\\r][\\n\\r]+|[\\r\\n]0\\s[\\r\\n]+",
+      std::regex_constants::ECMAScript | std::regex_constants::icase);
+  regex space_regex("[\\n\\s\\r]+", std::regex_constants::ECMAScript |
+                                        std::regex_constants::icase);
+  vector<string> sections = split(data, section_regex);
+  // for (int i = 0; i < sections.size(); i++) {
+  //  cout << "Section " << i << " " << sections[i].size() << endl;
+  //  cout << sections[i] << endl;
+  //}
+  return 0;
+}
+string readFile(const string& datapath) {
+  std::ifstream in(datapath, std::ios::in);
+  string data;
+  if (in.good()) {
+    std::string contents;
+    in.seekg(0, std::ios::end);
+    contents.resize(static_cast<unsigned int>(in.tellg()));
+    in.seekg(0, std::ios::beg);
+    in.read(&contents[0], contents.size());
+    return contents;
+  }
+  std::cerr << "Failed to open file: " << datapath << std::endl;
+  throw(errno);
+}
+vector<string> split(string s, regex r) {
+  vector<string> splits;
+  smatch m;  // <-- need a match object
+  while (regex_search(s, m, r))  // <-- use it here to get the match
+  {
+    int split_on = m.position();  // <-- use the match position
+    splits.push_back(s.substr(0, split_on));
+    s = s.substr(split_on + m.length());  // <-- also, skip the whole match
+  }
+  if (!s.empty()) {
+    splits.push_back(s);  // and there may be one last token at the end
+  }
+  return splits;
+}
+</syntaxhighlight>
+}}
 ==Hardware/Architecture==