From 2c424d29fd813b1fbef3b07595713611a1684903 Mon Sep 17 00:00:00 2001 From: bd Date: Sat, 8 Mar 2025 12:51:01 -0500 Subject: enforce single unit per clock cycle, order to serve storage requests --- inc/storage.h | 31 +++++- src/storage/dram.cc | 12 +-- src/storage/storage.cc | 11 ++- tests/dram.cc | 256 +++++++++++++++++++++++++++---------------------- 4 files changed, 180 insertions(+), 130 deletions(-) diff --git a/inc/storage.h b/inc/storage.h index a38f17d..95b6749 100644 --- a/inc/storage.h +++ b/inc/storage.h @@ -2,18 +2,35 @@ #define STORAGE_H #include "definitions.h" #include "response.h" +#include #include -#include +#include #include enum Accessor { MEM, FETCH, L1CACHE, - IDLE, SIDE, }; +/** + * Wrapper class for std::deque. + * + * Implements a deque that does not push duplicate objects. + */ +template class Deque : public std::deque +{ + public: + using std::deque::deque; + + void push_back(const T &value) + { + if (std::find(this->begin(), this->end(), value) == this->end()) + std::deque::push_back(value); + } +}; + class Storage { public: @@ -41,6 +58,10 @@ class Storage * is a word. */ std::vector> view(int base, int lines); + /** + * Advances to the next job if the current job is completed. + */ + void resolve(); protected: /** @@ -62,11 +83,11 @@ class Storage */ int delay; /** - * The accessor currently being serviced. + * The accessors currently being serviced, in first come first serve order. */ - enum Accessor servicing; + Deque deque; /** - * The number of cycles until the currently request is completed. + * The number of cycles until the current request is completed. */ int wait_time; }; diff --git a/src/storage/dram.cc b/src/storage/dram.cc index 4c4ca84..32f3fbb 100644 --- a/src/storage/dram.cc +++ b/src/storage/dram.cc @@ -2,14 +2,15 @@ #include "definitions.h" #include "response.h" #include +#include Dram::Dram(int lines, int delay) { this->data = new std::vector>; this->data->resize(lines); this->delay = delay; + this->wait_time = this->delay; this->lower = nullptr; - this->servicing = IDLE; } Dram::~Dram() { delete this->data; } @@ -23,17 +24,12 @@ Response Dram::write(Accessor accessor, signed int data, int address) r = OK; } else { /* Do this first--then process the first cycle immediately. */ - if (this->servicing == IDLE) { - this->servicing = accessor; - this->wait_time = delay; - } + this->deque.push_back(accessor); - if (this->servicing == accessor) { + if (this->deque.front() == accessor) { if (this->wait_time == 0) { this->do_write(data, address); r = OK; - } else { - --this->wait_time; } } } diff --git a/src/storage/storage.cc b/src/storage/storage.cc index 024699b..429ac2b 100644 --- a/src/storage/storage.cc +++ b/src/storage/storage.cc @@ -18,6 +18,15 @@ void Storage::do_write(signed data, int address) int line = address / LINE_SIZE; int word = address % LINE_SIZE; - this->servicing = IDLE; this->data->at(line).at(word) = data; } + +void Storage::resolve() +{ + if (this->wait_time == 0) { + this->deque.pop_front(); + this->wait_time = delay; + } else { + --this->wait_time; + } +} diff --git a/tests/dram.cc b/tests/dram.cc index ba81508..e0189c7 100644 --- a/tests/dram.cc +++ b/tests/dram.cc @@ -23,7 +23,7 @@ TEST_CASE( signed int w = 0x11223344; Response r = d->write(MEM, w, 0x00000000); - REQUIRE(r == OK); + CHECK(r == OK); expected.at(0) = w; actual = d->view(0, 1)[0]; @@ -35,34 +35,28 @@ TEST_CASE( TEST_CASE( "Construct singleton dram, store 0th element in three cycles", "[dram]") { - Dram *d = new Dram(1, 3); + int delay = 3; + Dram *d = new Dram(1, delay); std::array expected = {0, 0, 0, 0}; std::array actual = d->view(0, 1)[0]; CHECK(expected == actual); signed int w = 0x11223344; - // MEMORY CYCLE 1 - Response r = d->write(MEM, w, 0x00000000); - actual = d->view(0, 1)[0]; - REQUIRE(expected == actual); - REQUIRE(r == WAIT); + int i; + Response r; + for (i = 0; i < delay; ++i) { + r = d->write(MEM, w, 0x00000000); + CHECK(r == WAIT); - // MEMORY CYCLE 2 - r = d->write(MEM, w, 0x00000000); - actual = d->view(0, 1)[0]; - REQUIRE(expected == actual); - REQUIRE(r == WAIT); + actual = d->view(0, 1)[0]; + REQUIRE(expected == actual); + d->resolve(); + } - // MEMORY CYCLE 3 r = d->write(MEM, w, 0x00000000); - actual = d->view(0, 1)[0]; - REQUIRE(expected == actual); - REQUIRE(r == WAIT); - - // MEMORY CYCLE 4 - r = d->write(MEM, w, 0x00000000); - REQUIRE(r == OK); + CHECK(r == OK); + d->resolve(); expected.at(0) = w; actual = d->view(0, 1)[0]; @@ -76,66 +70,58 @@ TEST_CASE( "conflict", "[dram]") { - Dram *d = new Dram(1, 3); + int delay = 3; + Dram *d = new Dram(1, delay); std::array expected = {0, 0, 0, 0}; std::array actual = d->view(0, 1)[0]; CHECK(expected == actual); - signed int w1 = 0x11223344; - signed int w2 = 0x55667788; + signed int w = 0x11223344; - // MEMORY CYCLE 1 - Response r = d->write(MEM, w1, 0x00000000); - actual = d->view(0, 1)[0]; - REQUIRE(expected == actual); - REQUIRE(r == WAIT); + int i; + Response r; + for (i = 0; i < delay; ++i) { + r = d->write(MEM, w, 0x00000000); + CHECK(r == WAIT); - // MEMORY CYCLE 2 - actual = d->view(0, 1)[0]; - r = d->write(MEM, w1, 0x00000000); - actual = d->view(0, 1)[0]; - REQUIRE(expected == actual); - REQUIRE(r == WAIT); + actual = d->view(0, 1)[0]; + CHECK(r == WAIT); - // MEMORY CYCLE 3 - r = d->write(MEM, w1, 0x00000000); - actual = d->view(0, 1)[0]; - REQUIRE(expected == actual); - REQUIRE(r == WAIT); + REQUIRE(expected == actual); + d->resolve(); + } - // MEMORY CYCLE 4 - r = d->write(MEM, w1, 0x00000000); + r = d->write(MEM, w, 0x00000000); REQUIRE(r == OK); - // NOTE: servicing on the same clock cycle should probably not be allowed - // FETCH CYCLE 1 - r = d->write(FETCH, w2, 0x00000001); - actual = d->view(0, 1)[0]; - REQUIRE(r == WAIT); + // clock cycle did NOT resolve yet! + // this fetch should not make progress + r = d->write(FETCH, w, 0x00000001); + CHECK(r == WAIT); - expected.at(0) = w1; actual = d->view(0, 1)[0]; - CHECK(expected == actual); + CHECK(r == WAIT); + d->resolve(); - // FETCH CYCLE 2 - r = d->write(FETCH, w2, 0x00000001); + expected.at(0) = w; actual = d->view(0, 1)[0]; REQUIRE(expected == actual); - REQUIRE(r == WAIT); - // FETCH CYCLE 3 - r = d->write(FETCH, w2, 0x00000001); - actual = d->view(0, 1)[0]; - REQUIRE(expected == actual); - REQUIRE(r == WAIT); + for (i = 0; i < delay; ++i) { + r = d->write(FETCH, w, 0x00000001); + CHECK(r == WAIT); - // FETCH CYCLE 4 - r = d->write(FETCH, w2, 0x00000001); + actual = d->view(0, 1)[0]; + REQUIRE(expected == actual); + d->resolve(); + } + + r = d->write(FETCH, w, 0x00000001); actual = d->view(0, 1)[0]; - REQUIRE(r == OK); + CHECK(r == OK); - expected.at(1) = w2; + expected.at(1) = w; actual = d->view(0, 1)[0]; - CHECK(expected == actual); + REQUIRE(expected == actual); delete d; } @@ -145,103 +131,141 @@ TEST_CASE( "conflict", "[dram]") { - Dram *d = new Dram(1, 3); + int delay = 2; + Dram *d = new Dram(1, 2); std::array expected = {0, 0, 0, 0}; std::array actual = d->view(0, 1)[0]; CHECK(expected == actual); - signed int w1 = 0x11223344; - signed int w2 = 0x55667788; + signed int w = 0x11223344; - // MEMORY CYCLE 1 - Response r = d->write(MEM, w1, 0x00000000); - actual = d->view(0, 1)[0]; - REQUIRE(expected == actual); - REQUIRE(r == WAIT); + int i; + Response r; + for (i = 0; i < delay; ++i) { + r = d->write(MEM, w, 0x00000000); + CHECK(r == WAIT); + + r = d->write(FETCH, w, 0x00000001); + CHECK(r == WAIT); + + actual = d->view(0, 1)[0]; + REQUIRE(expected == actual); + d->resolve(); + } + + r = d->write(MEM, w, 0x00000000); + CHECK(r == OK); + r = d->write(FETCH, w, 0x00000001); + CHECK(r == WAIT); + d->resolve(); - // MEMORY CYCLE 2 - actual = d->view(0, 1)[0]; - r = d->write(MEM, w1, 0x00000000); actual = d->view(0, 1)[0]; + expected.at(0) = w; REQUIRE(expected == actual); - REQUIRE(r == WAIT); - // FETCH CYCLE 1 - r = d->write(FETCH, w2, 0x00000001); + + for (i = 0; i < delay; ++i) { + r = d->write(FETCH, w, 0x00000001); + CHECK(r == WAIT); + + r = d->write(MEM, w, 0x00000003); + CHECK(r == WAIT); + + actual = d->view(0, 1)[0]; + REQUIRE(expected == actual); + d->resolve(); + } + + r = d->write(FETCH, w, 0x00000001); actual = d->view(0, 1)[0]; - REQUIRE(r == WAIT); + CHECK(r == OK); + r = d->write(MEM, w, 0x00000003); + CHECK(r == WAIT); - r = d->write(MEM, w1, 0x00000000); + expected.at(1) = w; actual = d->view(0, 1)[0]; REQUIRE(expected == actual); - REQUIRE(r == WAIT); - // FETCH CYCLE 1 - r = d->write(FETCH, w2, 0x00000001); - actual = d->view(0, 1)[0]; - REQUIRE(r == WAIT); - r = d->write(MEM, w1, 0x00000000); - REQUIRE(r == OK); - // NOTE: servicing on the same clock cycle should probably not be allowed - // FETCH CYCLE 1 - r = d->write(FETCH, w2, 0x00000001); - actual = d->view(0, 1)[0]; - REQUIRE(r == WAIT); + delete d; +} - expected.at(0) = w1; - actual = d->view(0, 1)[0]; +TEST_CASE("Many conflicting requests first-come first serve", "[dram]") +{ + int delay = 1; + Dram *d = new Dram(1, delay); + std::array expected = {0, 0, 0, 0}; + std::array actual = d->view(0, 1)[0]; CHECK(expected == actual); - r = d->write(FETCH, w2, 0x00000001); + signed int w = 0x11223344; + + Response r; + r = d->write(FETCH, w, 0x00000000); + r = d->write(MEM, w, 0x00000001); + actual = d->view(0, 1)[0]; REQUIRE(expected == actual); - REQUIRE(r == WAIT); + d->resolve(); - r = d->write(FETCH, w2, 0x00000001); + r = d->write(FETCH, w, 0x00000000); + r = d->write(L1CACHE, w, 0x00000002); + // call mem after cache + r = d->write(MEM, w, 0x00000001); + + expected.at(0) = w; actual = d->view(0, 1)[0]; REQUIRE(expected == actual); - REQUIRE(r == WAIT); + d->resolve(); + + r = d->write(MEM, w, 0x00000001); + r = d->write(L1CACHE, w, 0x00000002); - r = d->write(FETCH, w2, 0x00000001); actual = d->view(0, 1)[0]; - REQUIRE(r == OK); + REQUIRE(expected == actual); + d->resolve(); - expected.at(1) = w2; + r = d->write(MEM, w, 0x00000001); + r = d->write(L1CACHE, w, 0x00000002); + + expected.at(1) = w; actual = d->view(0, 1)[0]; - CHECK(expected == actual); + REQUIRE(expected == actual); delete d; } TEST_CASE("Sidedoor bypasses delay", "[dram]") { - Dram *d = new Dram(1, 3); + int delay = 3; + Dram *d = new Dram(1, delay); std::array expected = {0, 0, 0, 0}; std::array actual = d->view(0, 1)[0]; CHECK(expected == actual); - signed int w1 = 0x11223344; - signed int w2 = 0x55667788; + signed int w = 0x11223344; + + int i; + Response r; + for (i = 0; i < delay - 1; ++i) { + r = d->write(MEM, w, 0x00000000); + CHECK(r == WAIT); - // MEMORY CYCLE 1 - Response r = d->write(MEM, w1, 0x00000000); - actual = d->view(0, 1)[0]; - REQUIRE(expected == actual); - REQUIRE(r == WAIT); + actual = d->view(0, 1)[0]; + REQUIRE(expected == actual); + d->resolve(); + } - // MEMORY CYCLE 2 - actual = d->view(0, 1)[0]; - r = d->write(MEM, w1, 0x00000000); + r = d->write(MEM, w, 0x00000000); + CHECK(r == WAIT); actual = d->view(0, 1)[0]; REQUIRE(expected == actual); - REQUIRE(r == WAIT); - // SIDE CYCLE 1 - r = d->write(SIDE, w2, 0x00000001); + + r = d->write(SIDE, w, 0x00000001); actual = d->view(0, 1)[0]; - REQUIRE(r == OK); + CHECK(r == OK); - expected.at(1) = w2; + expected.at(1) = w; actual = d->view(0, 1)[0]; - CHECK(expected == actual); + REQUIRE(expected == actual); delete d; } -- cgit v1.2.3