PandA-2024.02
examples
MachSuite
MachSuite
bfs
queue
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;
31
node_index_t
dst
;
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
{
46
node_t
nodes
[
N_NODES
];
47
edge_t
edges
[
N_EDGES
];
48
node_index_t
starting_node;
49
level_t
level
[
N_NODES
];
50
edge_index_t
level_counts[
N_LEVELS
];
51
};
52
53
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
]);
nodes
struct Node nodes[7]
Definition:
simple_raytrace.c:62
node_t
struct node_t_struct node_t
node_index_t
uint64_t node_index_t
Definition:
bfs.h:26
N_EDGES
#define N_EDGES
Definition:
bfs.h:18
edge_t_struct::dst
node_index_t dst
Definition:
bfs.h:32
level_t
int8_t level_t
Definition:
bfs.h:40
edges
unsigned edges[4545]
Definition:
graph.h:25
edge_index_t
uint64_t edge_index_t
Definition:
bfs.h:25
edge_t
struct edge_t_struct edge_t
node_t_struct
Definition:
bfs.h:35
N_LEVELS
#define N_LEVELS
Definition:
bfs.h:21
level
int level
Definition:
main.c:98
bfs
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
edge_t_struct
Definition:
bfs.h:28
bench_args_t
Definition:
aes.h:18
N_NODES
#define N_NODES
Definition:
bfs.h:17
Generated on Mon Feb 12 2024 13:02:49 for PandA-2024.02 by
1.8.13