gwr_engine/time/
clock.rs

1// Copyright (c) 2023 Graphcore Ltd. All rights reserved.
2
3//! This module represents the time during a simulation.
4//!
5//! Time is made up of a cycle count and a phase.
6
7use core::cmp::Ordering;
8use std::cell::{Cell, RefCell};
9use std::future::Future;
10use std::pin::Pin;
11use std::rc::Rc;
12use std::task::{Context, Poll, Waker};
13
14use crate::traits::{Resolve, Resolver};
15
16/// ClockTick structure for representing a number of Clock ticks and a phase.
17#[derive(Clone, Copy, Debug, PartialEq, Eq)]
18pub struct ClockTick {
19    /// Clock ticks.
20    tick: u64,
21
22    /// Clock phase.
23    #[cfg(feature = "phase")]
24    phase: u32,
25}
26
27impl ClockTick {
28    #[must_use]
29    pub fn new() -> Self {
30        Self {
31            tick: 0,
32
33            #[cfg(feature = "phase")]
34            phase: 0,
35        }
36    }
37
38    /// Get the current clock tick.
39    #[must_use]
40    pub fn tick(&self) -> u64 {
41        self.tick
42    }
43
44    /// Get the current clock phase.
45    #[must_use]
46    #[cfg(feature = "phase")]
47    pub fn phase(&self) -> u32 {
48        self.phase
49    }
50
51    /// Change the default constructor value of `tick`.
52    pub fn set_tick(&mut self, tick: u64) -> ClockTick {
53        self.tick = tick;
54        *self
55    }
56
57    /// Change the default constructor value of `phase`.
58    #[cfg(feature = "phase")]
59    pub fn set_phase(&mut self, phase: u32) -> ClockTick {
60        self.phase = phase;
61        *self
62    }
63}
64
65impl Default for ClockTick {
66    fn default() -> Self {
67        Self::new()
68    }
69}
70
71/// Define the comparison operation for SimTime.
72impl Ord for ClockTick {
73    #[cfg(feature = "phase")]
74    fn cmp(&self, other: &Self) -> Ordering {
75        match self.tick.cmp(&other.tick) {
76            Ordering::Greater => Ordering::Greater,
77            Ordering::Less => Ordering::Less,
78            Ordering::Equal => self.phase.cmp(&other.phase),
79        }
80    }
81
82    #[cfg(not(feature = "phase"))]
83    fn cmp(&self, other: &Self) -> Ordering {
84        self.tick.cmp(&other.tick)
85    }
86}
87
88impl PartialOrd for ClockTick {
89    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
90        Some(self.cmp(other))
91    }
92}
93
94impl std::fmt::Display for ClockTick {
95    #[cfg(feature = "phase")]
96    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
97        write!(f, "{}.{:?}", self.tick, self.phase)
98    }
99    #[cfg(not(feature = "phase"))]
100    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
101        write!(f, "{}", self.tick)
102    }
103}
104
105/// State representing a clock.
106#[derive(Clone)]
107pub struct Clock {
108    /// Frequency of the clock in MHz.
109    /// *Note*: Should never be changed as it is registered at this frequency.
110    freq_mhz: f64,
111
112    pub shared_state: Rc<ClockState>,
113}
114
115pub struct TaskWaker {
116    /// Internal identifier for a scheduled clock wait.
117    pub id: u64,
118
119    /// The Waker to use to make a task active again.
120    pub waker: Waker,
121
122    /// When a task is scheduled in the future it may be a background task
123    /// that will simply run forever in which case it will set `can_exit` to
124    /// true.
125    pub can_exit: bool,
126}
127
128/// Shared state between futures using a Clock and the Clock itself.
129pub struct ClockState {
130    now: RefCell<ClockTick>,
131
132    next_waiter_id: Cell<u64>,
133
134    /// Queue of futures waiting for the right time.
135    pub waiting: RefCell<Vec<Vec<TaskWaker>>>,
136
137    /// Queue of times at which those futures are to be woken. This is kept
138    /// sorted by time so that the first entry is the next to be woken.
139    pub waiting_times: RefCell<Vec<ClockTick>>,
140
141    /// Registered [`Resolve`] functions.
142    pub to_resolve: RefCell<Vec<Rc<dyn Resolve + 'static>>>,
143}
144
145impl ClockState {
146    fn schedule(&self, schedule_time: ClockTick, cx: &mut Context<'_>, can_exit: bool) -> u64 {
147        let waiter_id = self.next_waiter_id.get();
148        self.next_waiter_id.set(waiter_id + 1);
149
150        let mut waiting_times = self.waiting_times.borrow_mut();
151        let mut waiting = self.waiting.borrow_mut();
152        if let Some(index) = waiting_times.iter().position(|&x| x == schedule_time) {
153            // Time already exists, add this task
154            waiting[index].push(TaskWaker {
155                id: waiter_id,
156                waker: cx.waker().clone(),
157                can_exit,
158            });
159        } else {
160            // Time not found, insert at the correct location
161            match waiting_times.iter().position(|x| *x < schedule_time) {
162                Some(index) => {
163                    // Insert at an arbitrary index
164                    waiting_times.insert(index, schedule_time);
165                    waiting.insert(
166                        index,
167                        vec![TaskWaker {
168                            id: waiter_id,
169                            waker: cx.waker().clone(),
170                            can_exit,
171                        }],
172                    );
173                }
174                None => {
175                    // Insert at the head
176                    waiting_times.push(schedule_time);
177                    waiting.push(vec![TaskWaker {
178                        id: waiter_id,
179                        waker: cx.waker().clone(),
180                        can_exit,
181                    }]);
182                }
183            }
184        }
185
186        waiter_id
187    }
188
189    fn unschedule(&self, schedule_time: ClockTick, waiter_id: u64) {
190        let mut waiting_times = self.waiting_times.borrow_mut();
191        let mut waiting = self.waiting.borrow_mut();
192
193        if let Some(time_index) = waiting_times.iter().position(|&x| x == schedule_time)
194            && let Some(waiter_index) = waiting[time_index].iter().position(|w| w.id == waiter_id)
195        {
196            waiting[time_index].remove(waiter_index);
197            if waiting[time_index].is_empty() {
198                waiting.remove(time_index);
199                waiting_times.remove(time_index);
200            }
201        }
202    }
203
204    fn advance_time(&self, to_time: ClockTick) {
205        self.resolve();
206
207        assert!(to_time >= *self.now.borrow(), "Time moving backwards");
208        *self.now.borrow_mut() = to_time;
209    }
210
211    fn resolve(&self) {
212        for r in self.to_resolve.borrow_mut().drain(..) {
213            r.resolve();
214        }
215    }
216}
217
218impl Clock {
219    /// Create a new [Clock] at the specified frequency.
220    #[must_use]
221    pub fn new(freq_mhz: f64) -> Self {
222        let shared_state = Rc::new(ClockState {
223            now: RefCell::new(ClockTick {
224                tick: 0,
225                #[cfg(feature = "phase")]
226                phase: 0,
227            }),
228            next_waiter_id: Cell::new(0),
229            waiting: RefCell::new(Vec::new()),
230            waiting_times: RefCell::new(Vec::new()),
231            to_resolve: RefCell::new(Vec::new()),
232        });
233
234        Self {
235            freq_mhz,
236            shared_state,
237        }
238    }
239
240    /// Advance the time on this clock
241    pub fn advance_time(&self, to_time: ClockTick) {
242        self.shared_state.advance_time(to_time);
243    }
244
245    /// Returns the clocks frequency in MHz.
246    #[must_use]
247    pub fn freq_mhz(&self) -> f64 {
248        self.freq_mhz
249    }
250
251    /// Returns the current [ClockTick].
252    #[must_use]
253    pub fn tick_now(&self) -> ClockTick {
254        *self.shared_state.now.borrow()
255    }
256
257    /// Returns the current time in `ns`.
258    #[must_use]
259    pub fn time_now_ns(&self) -> f64 {
260        let now = *self.shared_state.now.borrow();
261        self.to_ns(&now)
262    }
263
264    /// Returns the time in `ns` of the next event registered with this clock.
265    #[must_use]
266    pub fn time_of_next(&self) -> f64 {
267        match self.shared_state.waiting_times.borrow().first() {
268            Some(clock_time) => self.to_ns(clock_time),
269            None => f64::MAX,
270        }
271    }
272
273    /// Convert the given [ClockTick] to a time in `ns` for this clock.
274    #[must_use]
275    pub fn to_ns(&self, clock_time: &ClockTick) -> f64 {
276        clock_time.tick as f64 / self.freq_mhz * 1000.0
277    }
278
279    /// Returns a [ClockDelay] future which must be `await`ed to delay the
280    /// specified number of ticks.
281    #[must_use = "Futures do nothing unless you `.await` or otherwise use them"]
282    pub fn wait_ticks(&self, ticks: u64) -> ClockDelay {
283        let mut until = self.tick_now();
284        until.tick += ticks;
285        ClockDelay {
286            shared_state: self.shared_state.clone(),
287            until,
288            can_exit: false,
289            waiter_id: None,
290        }
291    }
292
293    /// Returns a [ClockDelay] future which must be `await`ed to delay the
294    /// specified number of ticks. However, if the remainder of the simulation
295    /// completes then this future is allowed to not complete. This allows the
296    /// user to create tasks that can run continuously as long as the rest of
297    /// the simulation continues to run.
298    #[must_use = "Futures do nothing unless you `.await` or otherwise use them"]
299    pub fn wait_ticks_or_exit(&self, ticks: u64) -> ClockDelay {
300        let mut until = self.tick_now();
301        until.tick += ticks;
302        ClockDelay {
303            shared_state: self.shared_state.clone(),
304            until,
305            can_exit: true,
306            waiter_id: None,
307        }
308    }
309
310    #[must_use = "Futures do nothing unless you `.await` or otherwise use them"]
311    #[cfg(feature = "phase")]
312    pub fn next_tick_and_phase(&self, phase: u32) -> ClockDelay {
313        let mut until = self.tick_now();
314        until.tick += 1;
315        until.phase = phase;
316        ClockDelay {
317            shared_state: self.shared_state.clone(),
318            until,
319            can_exit: false,
320            waiter_id: None,
321        }
322    }
323
324    #[must_use = "Futures do nothing unless you `.await` or otherwise use them"]
325    #[cfg(feature = "phase")]
326    pub fn wait_phase(&self, phase: u32) -> ClockDelay {
327        let mut until = self.tick_now();
328        assert!(phase > until.phase, "Time going backwards");
329        until.phase = phase;
330        ClockDelay {
331            shared_state: self.shared_state.clone(),
332            until,
333            can_exit: false,
334            waiter_id: None,
335        }
336    }
337
338    /// Advance to the next tick after the specified time.
339    pub fn advance_to(&self, time_ns: f64) {
340        let now_ns = self.time_now_ns();
341        assert!(now_ns < time_ns);
342        let diff_ns = time_ns - now_ns;
343        let ticks = (diff_ns * (self.freq_mhz / 1000.0)).ceil();
344
345        let mut until = self.tick_now();
346        until.tick += ticks as u64;
347
348        self.shared_state.advance_time(until);
349    }
350}
351
352/// The default clocks is simply to use a 1GHz clock so ticks are 1ns.
353impl Default for Clock {
354    fn default() -> Self {
355        Self::new(1000.0)
356    }
357}
358
359/// The comparison operators for Clocks - use the next pending Waker time.
360impl PartialEq for Clock {
361    fn eq(&self, other: &Self) -> bool {
362        self.time_of_next() == other.time_of_next()
363    }
364}
365impl Eq for Clock {}
366
367impl Ord for Clock {
368    fn cmp(&self, other: &Self) -> Ordering {
369        if self.time_of_next() < other.time_of_next() {
370            Ordering::Less
371        } else {
372            Ordering::Greater
373        }
374    }
375}
376
377impl PartialOrd for Clock {
378    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
379        Some(self.cmp(other))
380    }
381}
382
383impl Resolver for Clock {
384    fn add_resolve(&self, resolve: Rc<dyn Resolve + 'static>) {
385        self.shared_state.to_resolve.borrow_mut().push(resolve);
386    }
387}
388
389/// Future returned by the clock to manage advancing time using async functions.
390pub struct ClockDelay {
391    shared_state: Rc<ClockState>,
392    until: ClockTick,
393    can_exit: bool,
394    waiter_id: Option<u64>,
395}
396
397impl Future for ClockDelay {
398    type Output = ();
399    fn poll(mut self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output> {
400        if self.until > *self.shared_state.now.borrow() {
401            if let Some(waiter_id) = self.waiter_id {
402                self.shared_state.unschedule(self.until, waiter_id);
403            }
404            let waiter_id = self.shared_state.schedule(self.until, cx, self.can_exit);
405            self.waiter_id = Some(waiter_id);
406            Poll::Pending
407        } else {
408            self.waiter_id = None;
409            Poll::Ready(())
410        }
411    }
412}
413
414impl Drop for ClockDelay {
415    fn drop(&mut self) {
416        if let Some(waiter_id) = self.waiter_id.take() {
417            self.shared_state.unschedule(self.until, waiter_id);
418        }
419    }
420}
421
422#[cfg(test)]
423mod tests {
424    use super::*;
425
426    #[test]
427    fn convert_to_ns() {
428        let clk_ghz = Clock::new(1000.0);
429        assert_eq!(1.0, clk_ghz.to_ns(&ClockTick::new().set_tick(1)));
430
431        let slow_clk = Clock::new(0.5);
432        assert_eq!(2000.0, slow_clk.to_ns(&ClockTick::new().set_tick(1)));
433    }
434}
gwr_engine/time/clock.rs

gwr_engine/time/
clock.rs
