doc/div_pipeline_loop_model/src/main.ts

   1 // WIP pipeline loop demo
   2
   3 let instruction_queue: (null | Instruction)[] = [];
   4 let instruction_cancel_queue: (null | Instruction[])[] = [];
   5
   6 class Instruction {
   7     pc: number;
   8     reservation_station: null | ReservationStation;
   9     canceled: boolean;
  10     constructor(pc: number) {
  11         this.pc = pc;
  12         this.reservation_station = null;
  13         this.canceled = false;
  14     }
  15     toString() {
  16         return `0x${this.pc.toString(16)}`
  17     }
  18 }
  19
  20 class StageConnectionPoint {
  21     stage: Stage;
  22     x: number;
  23     y: number;
  24     constructor(stage: Stage, x: number, y: number) {
  25         this.stage = stage;
  26         this.x = x;
  27         this.y = y;
  28     }
  29 }
  30
  31 const enum State {
  32     Empty,
  33     Starting,
  34     Executing,
  35     Canceling,
  36     Finished,
  37     Stalled,
  38 }
  39
  40 function assert_unreachable(v: never): never { return v; }
  41
  42 let diagram: HTMLElement;
  43 class Stage {
  44     static readonly GRID_CELL_WIDTH = 100;
  45     static readonly GRID_CELL_HEIGHT = 50;
  46     static readonly BOX_WIDTH = 90;
  47     static readonly BOX_HEIGHT = 40;
  48     static readonly ALL_STAGES: Stage[] = [];
  49     x: number;
  50     y: number;
  51     name: string;
  52     instruction: Instruction | null;
  53     group_node: SVGGElement;
  54     box_node: SVGRectElement;
  55     name_node: SVGTextElement;
  56     status_text_node: SVGTextElement;
  57     instruction_text_node: SVGTextElement;
  58     top_connection_point: StageConnectionPoint;
  59     bottom_connection_point: StageConnectionPoint;
  60     left_connection_point: StageConnectionPoint;
  61     right_connection_point: StageConnectionPoint;
  62     state: State = State.Empty;
  63     constructor(x: number, y: number, name: string) {
  64         Stage.ALL_STAGES.push(this);
  65         this.x = x;
  66         this.y = y;
  67         this.name = name;
  68         this.instruction = null;
  69         this.group_node = document.createElementNS("http://www.w3.org/2000/svg", "g");
  70         this.box_node = document.createElementNS("http://www.w3.org/2000/svg", "rect");
  71         this.box_node.setAttribute("width", String(Stage.BOX_WIDTH));
  72         this.box_node.setAttribute("height", String(Stage.BOX_HEIGHT));
  73         this.box_node.setAttribute("fill", "white");
  74         this.box_node.setAttribute("stroke", "black");
  75         this.box_node.setAttribute("x", String(x));
  76         this.box_node.setAttribute("y", String(y));
  77         this.group_node.appendChild(this.box_node);
  78         this.name_node = document.createElementNS("http://www.w3.org/2000/svg", "text");
  79         this.name_node.setAttribute("x", String(x + 5));
  80         this.name_node.setAttribute("y", String(y + 5));
  81         this.name_node.setAttribute("class", "stage_title");
  82         this.name_node.textContent = name;
  83         this.group_node.appendChild(this.name_node);
  84         this.status_text_node = document.createElementNS("http://www.w3.org/2000/svg", "text");
  85         this.status_text_node.setAttribute("x", String(x + 5));
  86         this.status_text_node.setAttribute("y", String(y + Stage.BOX_HEIGHT - 5));
  87         this.status_text_node.setAttribute("class", "stage_status_text");
  88         this.status_text_node.textContent = "";
  89         this.group_node.appendChild(this.status_text_node);
  90         this.instruction_text_node = document.createElementNS("http://www.w3.org/2000/svg", "text");
  91         this.instruction_text_node.setAttribute("x", String(x + Stage.BOX_WIDTH - 5));
  92         this.instruction_text_node.setAttribute("y", String(y + 5));
  93         this.instruction_text_node.setAttribute("class", "stage_instruction_text");
  94         this.instruction_text_node.textContent = "";
  95         this.group_node.appendChild(this.instruction_text_node);
  96         diagram.appendChild(this.group_node);
  97         this.top_connection_point = new StageConnectionPoint(this, x + Stage.BOX_WIDTH / 2, y);
  98         this.bottom_connection_point = new StageConnectionPoint(this, x + Stage.BOX_WIDTH / 2, y + Stage.BOX_HEIGHT);
  99         this.left_connection_point = new StageConnectionPoint(this, x, y + Stage.BOX_HEIGHT / 2);
 100         this.right_connection_point = new StageConnectionPoint(this, x + Stage.BOX_WIDTH, y + Stage.BOX_HEIGHT / 2);
 101         this.state = State.Empty;
 102     }
 103     update_visible_state() {
 104         let bk_color;
 105         let status_text;
 106         switch (this.state) {
 107             case State.Empty:
 108                 status_text = "empty"; bk_color = "#FFFFFF";
 109                 break;
 110             case State.Starting:
 111                 status_text = "starting"; bk_color = "#C0C000";
 112                 break;
 113             case State.Executing:
 114                 status_text = "executing"; bk_color = "#80FF80";
 115                 break;
 116             case State.Canceling:
 117                 status_text = "canceling"; bk_color = "#C04040";
 118                 break;
 119             case State.Finished:
 120                 status_text = "finished"; bk_color = "#8080FF";
 121                 break;
 122             case State.Stalled:
 123                 status_text = "stalled"; bk_color = "#909090";
 124                 break;
 125             default:
 126                 return assert_unreachable(this.state);
 127         }
 128         this.box_node.setAttribute("fill", bk_color);
 129         this.status_text_node.textContent = status_text;
 130         this.instruction_text_node.textContent = String(this.instruction || "");
 131     }
 132     tick_setup() { }
 133     tick() { }
 134 }
 135
 136 class ReservationStation extends Stage {
 137     next_state: State;
 138     constructor(x: number, y: number, name: string) {
 139         super(x, y, name);
 140         this.state = State.Empty;
 141         this.next_state = State.Empty;
 142     }
 143     tick_setup() {
 144         this.next_state = this.state;
 145         switch (this.state) {
 146             case State.Empty:
 147                 break;
 148             case State.Starting:
 149                 if (this.instruction!.canceled) {
 150                     this.next_state = State.Canceling;
 151                 }
 152                 else if (setup_stage.instruction === this.instruction) {
 153                     this.next_state = State.Executing;
 154                 }
 155                 break;
 156             case State.Executing:
 157                 if (this.instruction!.canceled) {
 158                     this.next_state = State.Canceling;
 159                 }
 160                 else if (finish_stage.instruction === this.instruction) {
 161                     this.next_state = State.Finished;
 162                 }
 163                 break;
 164             case State.Canceling:
 165                 this.next_state = State.Empty;
 166                 break;
 167             case State.Finished:
 168                 this.next_state = State.Empty;
 169                 break;
 170             default:
 171                 throw new TypeError("invalid state value");
 172         }
 173     }
 174     tick() {
 175         switch (this.state) {
 176             case State.Empty:
 177                 if (instruction_queue[0]) {
 178                     instruction_queue[0].reservation_station = this;
 179                     this.instruction = instruction_queue[0];
 180                     instruction_queue[0] = null;
 181                     this.state = State.Starting;
 182                 }
 183                 break;
 184             case State.Starting:
 185             case State.Executing:
 186                 this.state = this.next_state;
 187                 break;
 188             case State.Canceling:
 189                 this.instruction!.reservation_station = null;
 190                 this.instruction = null;
 191                 this.state = State.Empty;
 192                 break;
 193             case State.Finished:
 194                 this.instruction!.reservation_station = null;
 195                 this.instruction = null;
 196                 this.state = State.Empty;
 197                 break;
 198             default:
 199                 throw new TypeError("invalid state value");
 200         }
 201     }
 202 }
 203
 204 class LoopHeaderStage extends Stage {
 205     next_state: State;
 206     next_instruction: Instruction | null;
 207     constructor(x: number, y: number) {
 208         super(x, y, "loop hdr");
 209         this.state = State.Empty;
 210         this.next_state = State.Empty;
 211         this.next_instruction = null;
 212     }
 213 }
 214
 215 class LoopFooterStage extends Stage {
 216     next_state: State;
 217     next_instruction: Instruction | null;
 218     constructor(x: number, y: number) {
 219         super(x, y, "loop ftr");
 220         this.state = State.Empty;
 221         this.next_state = State.Empty;
 222         this.next_instruction = null;
 223     }
 224 }
 225
 226 class ComputeStage extends Stage {
 227     next_state: State;
 228     next_instruction: Instruction | null;
 229     constructor(x: number, y: number, name: string) {
 230         super(x, y, name);
 231         this.state = State.Empty;
 232         this.next_state = State.Empty;
 233         this.next_instruction = null;
 234     }
 235 }
 236
 237 class FinishStage extends Stage {
 238     next_state: State;
 239     next_instruction: Instruction | null;
 240     constructor(x: number, y: number) {
 241         super(x, y, "finish");
 242         this.state = State.Empty;
 243         this.next_state = State.Empty;
 244         this.next_instruction = null;
 245     }
 246 }
 247
 248 class SetupStage extends Stage {
 249     next_state: State;
 250     next_instruction: Instruction | null;
 251     stalled: boolean;
 252     constructor(x: number, y: number) {
 253         super(x, y, "setup");
 254         this.state = State.Empty;
 255         this.next_state = State.Empty;
 256         this.next_instruction = null;
 257         this.stalled = false;
 258     }
 259     tick_setup() {
 260         this.next_state = this.state;
 261         this.next_instruction = this.instruction;
 262         switch (this.state) {
 263             case State.Empty:
 264                 for (let rs of reservation_stations) {
 265                     if (rs.state == State.Starting) {
 266                         this.next_instruction = rs.instruction;
 267                         this.next_state = State.Executing;
 268                         break;
 269                     }
 270                 }
 271                 break;
 272             case State.Executing:
 273                 break;
 274             case State.Canceling:
 275                 this.next_state = State.Empty;
 276                 this.next_instruction = null;
 277                 break;
 278             default:
 279                 throw new TypeError("invalid state value");
 280         }
 281     }
 282     tick() {
 283         switch (this.state) {
 284             case State.Empty:
 285                 for (let rs of reservation_stations) {
 286
 287                 }
 288                 break;
 289             case State.Stalled:
 290                 break;
 291             case State.Executing:
 292                 break;
 293             case State.Canceling:
 294                 break;
 295             default:
 296                 throw new TypeError("invalid state value");
 297         }
 298     }
 299 }
 300
 301 class Connection {
 302     src_connection_point: StageConnectionPoint;
 303     dst_connection_point: StageConnectionPoint;
 304     path: { x: number | undefined; y: number | undefined; }[];
 305     node: SVGPolylineElement;
 306     constructor(src_connection_point: StageConnectionPoint, dst_connection_point: StageConnectionPoint, path: { x: number | undefined; y: number | undefined; }[]) {
 307         this.src_connection_point = src_connection_point;
 308         this.dst_connection_point = dst_connection_point;
 309         this.path = path;
 310         this.node = document.createElementNS("http://www.w3.org/2000/svg", "polyline");
 311         let points = [[src_connection_point.x, src_connection_point.y]];
 312         let x = src_connection_point.x;
 313         let y = src_connection_point.y;
 314         for (let path_element of path) {
 315             if (path_element.x !== undefined) {
 316                 x = path_element.x;
 317                 points.push([x, y]);
 318             }
 319             if (path_element.y !== undefined) {
 320                 y = path_element.y;
 321                 points.push([x, y]);
 322             }
 323         }
 324         points.push([dst_connection_point.x, y]);
 325         points.push([dst_connection_point.x, dst_connection_point.y]);
 326         let points_str = points.map(v => v.join()).join(" ");
 327         this.node.setAttribute("class", "connection");
 328         this.node.setAttribute("points", points_str);
 329         this.node.textContent = name;
 330         diagram.appendChild(this.node);
 331     }
 332 }
 333
 334 let reservation_stations: ReservationStation[] = [];
 335 let setup_stage: SetupStage;
 336 let finish_stage: FinishStage;
 337 let loop_stages: ComputeStage[] = [];
 338 let loop_header_stage: LoopHeaderStage;
 339 let loop_footer_stage: LoopFooterStage;
 340 let next_pc = 0x1000;
 341
 342 function add_instructions() {
 343     if (instruction_queue.length < 10) {
 344         let instr = new Instruction(next_pc);
 345         next_pc += 4;
 346         instruction_queue.push(instr);
 347         if (Math.random() < 0.4) {
 348             let cancel_time = Math.floor(Math.random() * 10) + 1;
 349             if (!instruction_cancel_queue[cancel_time]) {
 350                 instruction_cancel_queue[cancel_time] = [];
 351             }
 352             instruction_cancel_queue[cancel_time]!.push(instr);
 353         }
 354     }
 355 }
 356
 357 function cancel_instructions() {
 358     if (instruction_cancel_queue.length) {
 359         let first = instruction_cancel_queue.shift();
 360         if (first) {
 361             for (let i of first) {
 362                 i.canceled = true;
 363             }
 364         }
 365     }
 366 }
 367
 368 function tick() {
 369     add_instructions();
 370     cancel_instructions();
 371     for (let i of Stage.ALL_STAGES) {
 372         i.tick_setup();
 373     }
 374     for (let i of Stage.ALL_STAGES) {
 375         i.tick();
 376     }
 377     if (instruction_queue[0] === undefined)
 378         instruction_queue.shift();
 379     update_visible_state();
 380 }
 381
 382 function update_visible_state() {
 383     for (let i of Stage.ALL_STAGES) {
 384         i.update_visible_state();
 385     }
 386 }
 387
 388 function load() {
 389     diagram = document.getElementById("diagram")!;
 390     let loop_stage_count = 3;
 391     setup_stage = new SetupStage(Stage.GRID_CELL_WIDTH, 2 * Stage.GRID_CELL_HEIGHT);
 392     let reservation_station_count = 7;
 393     for (let i = 0; i < 7; i++) {
 394         let stage = new ReservationStation(0, Stage.GRID_CELL_HEIGHT * i, `rs${i}`);
 395         reservation_stations.push(stage);
 396         new Connection(stage.right_connection_point, setup_stage.left_connection_point,
 397             [{ x: Stage.BOX_WIDTH + 3, y: setup_stage.left_connection_point.y }]);
 398     }
 399     loop_header_stage = new LoopHeaderStage(Stage.GRID_CELL_WIDTH * 2, 2 * Stage.GRID_CELL_HEIGHT);
 400     new Connection(setup_stage.right_connection_point, loop_header_stage.left_connection_point, []);
 401     let prev_stage = loop_header_stage;
 402     for (let i = 0; i < loop_stage_count; i++) {
 403         let stage = new ComputeStage(Stage.GRID_CELL_WIDTH * (3 + i), 2 * Stage.GRID_CELL_HEIGHT, `compute${i}`);
 404         loop_stages.push(stage);
 405         new Connection(prev_stage.right_connection_point, stage.left_connection_point, []);
 406         prev_stage = stage;
 407     }
 408     loop_footer_stage = new LoopFooterStage(Stage.GRID_CELL_WIDTH * (3 + loop_stage_count), 2 * Stage.GRID_CELL_HEIGHT);
 409     new Connection(prev_stage.right_connection_point, loop_footer_stage.left_connection_point, []);
 410     new Connection(loop_footer_stage.bottom_connection_point, loop_header_stage.bottom_connection_point,
 411         [{ x: loop_footer_stage.bottom_connection_point.x, y: 3 * Stage.GRID_CELL_HEIGHT + 5 }]);
 412     finish_stage = new FinishStage(Stage.GRID_CELL_WIDTH * (4 + loop_stage_count), 2 * Stage.GRID_CELL_HEIGHT);
 413     new Connection(loop_footer_stage.right_connection_point, finish_stage.left_connection_point, []);
 414     for (let rs of reservation_stations) {
 415         new Connection(finish_stage.top_connection_point, rs.left_connection_point,
 416             [{ x: finish_stage.top_connection_point.x, y: -5 }, { x: -7, y: rs.left_connection_point.y }]);
 417     }
 418     setInterval(tick, 1500);
 419     update_visible_state();
 420 }