PandA-2024.02
bfs.h
Go to the documentation of this file.
1 /*
2 Implementation based on:
3 Hong, Oguntebi, Olukotun. "Efficient Parallel Graph Exploration on Multi-Core CPU and GPU." PACT, 2011.
4 */
5 
6 #include <stdlib.h>
7 #include <inttypes.h>
8 #include <stdio.h>
9 #include <string.h>
10 #include "support.h"
11 
12 // Terminology (but not values) from graph500 spec
13 // graph density = 2^-(2*SCALE - EDGE_FACTOR)
14 #define SCALE 8
15 #define EDGE_FACTOR 16
16 
17 #define N_NODES (1<<SCALE)
18 #define N_EDGES (N_NODES*EDGE_FACTOR)
19 
20 // upper limit
21 #define N_LEVELS 10
22 
23 // Larger than necessary for small graphs, but appropriate for large ones
24 typedef uint64_t edge_index_t;
25 typedef uint64_t node_index_t;
26 
27 typedef struct edge_t_struct {
28  // These fields are common in practice, but we elect not to use them.
29  //weight_t weight;
30  //node_index_t src;
32 } edge_t;
33 
34 typedef struct node_t_struct {
35  edge_index_t edge_begin;
36  edge_index_t edge_end;
37 } node_t;
38 
39 typedef int8_t level_t;
40 #define MAX_LEVEL INT8_MAX
41 
43 // Test harness interface code.
44 
45 struct bench_args_t {
48  node_index_t starting_node;
50  edge_index_t level_counts[N_LEVELS];
51 };
52 
struct Node nodes[7]
struct node_t_struct node_t
uint64_t node_index_t
Definition: bfs.h:26
#define N_EDGES
Definition: bfs.h:18
node_index_t dst
Definition: bfs.h:32
int8_t level_t
Definition: bfs.h:40
unsigned edges[4545]
Definition: graph.h:25
uint64_t edge_index_t
Definition: bfs.h:25
struct edge_t_struct edge_t
#define N_LEVELS
Definition: bfs.h:21
int level
Definition: main.c:98
void bfs(node_t nodes[N_NODES], edge_t edges[N_EDGES], node_index_t starting_node, level_t level[N_NODES], edge_index_t level_counts[N_LEVELS])
Definition: bfs.c:9
#define N_NODES
Definition: bfs.h:17

Generated on Mon Feb 12 2024 13:02:49 for PandA-2024.02 by doxygen 1.8.13