1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
use crate::nam_args_api::AccessIntent;
use crate::recording::queue::TaskQueue;
use crate::recording::task::RawTask;
use std::collections::HashMap;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum HazardType {
RAW,
WAR,
WAW,
}
#[derive(Debug, Clone)]
pub struct DependencyEdge {
pub source_task: usize,
pub destination_task: usize,
pub resource_slot: u32,
pub hazard_type: HazardType,
}
pub struct DependencyGraph {
pub tasks_count: usize,
pub edges: Vec<DependencyEdge>,
}
impl DependencyGraph {
pub fn build<'a>(queue: &TaskQueue<'a>) -> Self {
let tasks_count = queue.tasks.len();
let mut edges = Vec::new();
struct ResourceAccessHistory {
last_writer: Option<usize>,
last_readers: Vec<usize>,
}
let mut history_map: HashMap<u32, ResourceAccessHistory> = HashMap::new();
for (curr_idx, task) in queue.tasks.iter().enumerate() {
match task {
RawTask::Compute(t) => {
for bound_res in &t.args_ctx.bound_resources {
let slot = bound_res.slot_index;
let is_write = matches!(
bound_res.intent,
AccessIntent::Write | AccessIntent::ReadWrite
);
let history =
history_map
.entry(slot)
.or_insert_with(|| ResourceAccessHistory {
last_writer: None,
last_readers: Vec::new(),
});
if is_write {
for &reader_idx in &history.last_readers {
if reader_idx != curr_idx {
edges.push(DependencyEdge {
source_task: reader_idx,
destination_task: curr_idx,
resource_slot: slot,
hazard_type: HazardType::WAR,
});
}
}
if let Some(writer_idx) = history.last_writer
&& writer_idx != curr_idx
{
edges.push(DependencyEdge {
source_task: writer_idx,
destination_task: curr_idx,
resource_slot: slot,
hazard_type: HazardType::WAW,
});
}
history.last_writer = Some(curr_idx);
history.last_readers.clear();
} else {
if let Some(writer_idx) = history.last_writer
&& writer_idx != curr_idx
{
edges.push(DependencyEdge {
source_task: writer_idx,
destination_task: curr_idx,
resource_slot: slot,
hazard_type: HazardType::RAW,
});
}
history.last_readers.push(curr_idx);
}
}
}
RawTask::PresentBuffer(p) => {
let slot = p.buffer_id;
let history =
history_map
.entry(slot)
.or_insert_with(|| ResourceAccessHistory {
last_writer: None,
last_readers: Vec::new(),
});
if let Some(writer_idx) = history.last_writer
&& writer_idx != curr_idx
{
edges.push(DependencyEdge {
source_task: writer_idx,
destination_task: curr_idx,
resource_slot: slot,
hazard_type: HazardType::RAW,
});
}
history.last_readers.push(curr_idx);
}
RawTask::WriteTimestamp { .. } => {}
}
}
Self { tasks_count, edges }
}
}