Implement LRU cache replacement policy
MODIFY
src/cachebase.cpp
src/cachebase.cpp
namespace Ripes {
-void CacheBase::updateCacheValue(uint32_t address, uint32_t value) {
+void CacheBase::updateCacheLineLRU(CacheLine& line, unsigned lruIdx) {
+ // Find previous LRU value for the updated index
+ const unsigned preLRU = line[lruIdx].lru;
+
+ // All indicies which are curently more recent than preLRU shall be incremented
+ for (auto& set : line) {
+ if (set.second.valid && set.second.lru < preLRU) {
+ set.second.lru++;
+ }
+ }
+
+ // Upgrade @p lruIdx to the most recently used
+ line[lruIdx].lru = 0;
+}
+
+void CacheBase::updateCacheValue(uint32_t address) {
const unsigned lineIdx = getAccessLineIdx();
const unsigned blockIdx = getAccessBlockIdx();
@@ -14,21 +29,63 @@ void CacheBase::updateCacheValue(uint32_t address, uint32_t value) {
// Update based on replacement policy
if (m_policy == CacheReplPlcy::Random) {
// Select a random way
- const unsigned wayIdx = std::rand() % getSets();
- auto& way = cacheLine[wayIdx];
+ m_currentSetIdx = std::rand() % getSets();
+ auto& way = cacheLine[m_currentSetIdx];
// Todo: this is not valid; the entire cache line (all blocks) should be read
way.valid = true;
- emit dataChanged(address);
+ way.tag = getAccessTag();
+ } else if (m_policy == CacheReplPlcy::LRU) {
+ if (getSets() == 1) {
+ // Nothing to do if we are in LRU and only have 1 set
+ m_currentSetIdx = 0;
+ cacheLine[m_currentSetIdx].valid = true;
+ cacheLine[m_currentSetIdx].tag = getAccessTag();
+ return;
+ }
+
+ // Ensure that all ways in the cache line has been initialized
+ for (int i = 0; i < getSets(); i++) {
+ cacheLine[i];
+ }
+
+ // If there is an invalid cache line, select that
+ unsigned wayIdx = 0;
+ CacheWay* selectedWay = nullptr;
+ for (auto& way : cacheLine) {
+ if (!way.second.valid) {
+ wayIdx = way.first;
+ selectedWay = &way.second;
+ break;
+ }
+ }
+ if (selectedWay == nullptr) {
+ // Else, Find LRU way
+ for (auto& way : cacheLine) {
+ if (way.second.lru == getSets() - 1) {
+ wayIdx = way.first;
+ selectedWay = &way.second;
+ }
+ }
+ }
+
+ Q_ASSERT(selectedWay != nullptr && "There must have been an issue with setting the LRU bits");
+
+ m_currentSetIdx = wayIdx;
+ selectedWay->valid = true;
+ selectedWay->tag = getAccessTag();
+ updateCacheLineLRU(cacheLine, wayIdx);
}
}
-bool CacheBase::checkCacheHit() {
+bool CacheBase::analyzeCacheHit() {
const unsigned lineIdx = getAccessLineIdx();
+ m_currentAccessLine = &m_cacheLines[lineIdx];
+
if (m_cacheLines.count(lineIdx) != 0) {
int setIdx = 0;
for (const auto& way : m_cacheLines.at(lineIdx)) {
- if (way.second.tag == getAccessTag()) {
+ if (way.second.tag == getAccessTag() && way.second.valid) {
m_currentSetIdx = setIdx;
return true;
}
@@ -40,7 +97,10 @@ bool CacheBase::checkCacheHit() {
void CacheBase::read(uint32_t address) {
m_currentAccessAddress = address;
- m_currentAccessIsHit = checkCacheHit();
+ m_currentAccessIsHit = analyzeCacheHit();
+ if (!m_currentAccessIsHit) {
+ updateCacheValue(m_currentAccessAddress);
+ }
emit dataChanged(m_currentAccessAddress);
}
void CacheBase::write(uint32_t address) {
@@ -60,7 +120,7 @@ unsigned CacheBase::getAccessSetIdx() const {
}
unsigned CacheBase::getAccessTag() const {
- uint32_t maskedAddress = m_currentAccessAddress & m_lineMask;
+ uint32_t maskedAddress = m_currentAccessAddress & m_tagMask;
maskedAddress >>= 2 + getBlockBits() + getLineBits();
return maskedAddress;
}
@@ -72,6 +132,9 @@ unsigned CacheBase::getAccessBlockIdx() const {
}
void CacheBase::updateConfiguration() {
+ // Cache configuration changes shall enforce a full reset of the computing system
+ m_cacheLines.clear();
+
// Recalculate masks
int bitoffset = 2; // 2^2 = 4-byte offset (32-bit words in cache)

MODIFY
src/cachebase.h
src/cachebase.h
namespace Ripes {
enum class CacheReplPlcy { Random, LRU };
+static std::map<CacheReplPlcy, QString> CachePolicyStrings{{CacheReplPlcy::Random, "Random"},
+ {CacheReplPlcy::LRU, "LRU"}};
class CacheBase : public QObject {
Q_OBJECT
public:
CacheBase(QObject* parent) : QObject(parent) {}
+ void setReplacementPolicy(CacheReplPlcy policy) {
+ m_policy = policy;
+ updateConfiguration();
+ }
+
void read(uint32_t address);
void write(uint32_t address);
void undo();
+ CacheReplPlcy getReplacementPolicy() const { return m_policy; }
+
int getSizeInBits();
int getBlockBits() const { return m_blocks; }
@@ -56,11 +65,11 @@ signals:
void dataChanged(uint32_t address);
private:
- void updateCacheValue(uint32_t address, uint32_t value);
- bool checkCacheHit();
+ void updateCacheValue(uint32_t address);
+ bool analyzeCacheHit();
void updateConfiguration();
- CacheReplPlcy m_policy = CacheReplPlcy::Random;
+ CacheReplPlcy m_policy = CacheReplPlcy::LRU;
uint32_t m_currentAccessAddress;
bool m_currentAccessIsHit;
unsigned m_currentSetIdx;
@@ -70,19 +79,28 @@ private:
unsigned m_tagMask;
int m_blocks = 1; // Some power of 2
- int m_lines = 4; // Some power of 2
- int m_sets = 0; // Some power of 2
+ int m_lines = 2; // Some power of 2
+ int m_sets = 2; // Some power of 2
struct CacheWay {
uint32_t tag;
// std::map<unsigned, uint32_t> blocks; we do not store the actual data; no reason to!
bool dirty = false;
- bool valid = true;
- unsigned lru = 0;
+ bool valid = false;
+
+ // LRU algorithm relies on invalid cache ways to have an initial high value. -1 ensures maximum value for all
+ // set sizes.
+ unsigned lru = -1;
};
using CacheLine = std::map<unsigned, CacheWay>;
std::map<unsigned, CacheLine> m_cacheLines;
+
+ void updateCacheLineLRU(CacheLine& line, unsigned lruIdx);
+ CacheLine const* m_currentAccessLine = nullptr;
+
+public:
+ const CacheLine* getCurrentAccessLine() const { return m_currentAccessLine; }
};
} // namespace Ripes

MODIFY
src/cacheconfigwidget.ui
src/cacheconfigwidget.ui
<item>
<widget class="QGroupBox" name="groupBox">
<property name="title">
- <string>Cache configuration</string>
+ <string>Cache configuration:</string>
</property>
<layout class="QGridLayout" name="gridLayout_3">
<item row="0" column="0">
<layout class="QGridLayout" name="gridLayout">
- <item row="1" column="1">
- <widget class="QSpinBox" name="sets">
+ <item row="5" column="0">
+ <widget class="QCheckBox" name="checkBox">
+ <property name="text">
+ <string>Valid bit</string>
+ </property>
+ </widget>
+ </item>
+ <item row="0" column="1">
+ <widget class="QComboBox" name="presets"/>
+ </item>
+ <item row="3" column="1">
+ <widget class="QSpinBox" name="lines">
<property name="maximum">
<number>10</number>
</property>
</widget>
</item>
- <item row="3" column="0">
- <widget class="QLabel" name="label_4">
- <property name="text">
- <string>Lines</string>
+ <item row="2" column="1">
+ <widget class="QSpinBox" name="blocks">
+ <property name="maximum">
+ <number>10</number>
</property>
</widget>
</item>
- <item row="1" column="0">
- <widget class="QLabel" name="label_2">
+ <item row="3" column="0">
+ <widget class="QLabel" name="label_4">
<property name="text">
- <string>Sets</string>
+ <string>Lines</string>
</property>
</widget>
</item>
- <item row="0" column="1">
- <widget class="QComboBox" name="presets"/>
- </item>
<item row="2" column="0">
<widget class="QLabel" name="label_3">
<property name="text">
</property>
</widget>
</item>
- <item row="3" column="1">
- <widget class="QSpinBox" name="lines">
+ <item row="1" column="1">
+ <widget class="QSpinBox" name="sets">
<property name="maximum">
<number>10</number>
</property>
</widget>
</item>
+ <item row="1" column="0">
+ <widget class="QLabel" name="label_2">
+ <property name="text">
+ <string>Sets</string>
+ </property>
+ </widget>
+ </item>
<item row="0" column="0">
<widget class="QLabel" name="label">
<property name="text">
</property>
</widget>
</item>
- <item row="2" column="1">
- <widget class="QSpinBox" name="blocks">
- <property name="maximum">
- <number>10</number>
+ <item row="5" column="1">
+ <widget class="QCheckBox" name="checkBox_2">
+ <property name="toolTip">
+ <string>Setting the valid bit implies a write-back cache</string>
+ </property>
+ <property name="text">
+ <string>Dirty bit (WB)</string>
</property>
</widget>
</item>
<item row="4" column="0">
- <widget class="QCheckBox" name="checkBox">
+ <widget class="QLabel" name="label_8">
<property name="text">
- <string>Valid bit</string>
+ <string>Repl. policy:</string>
</property>
</widget>
</item>
<item row="4" column="1">
- <widget class="QCheckBox" name="checkBox_2">
- <property name="text">
- <string>Dirty bit</string>
- </property>
- </widget>
+ <widget class="QComboBox" name="replacementPolicy"/>
</item>
</layout>
</item>
<item>
<widget class="QGroupBox" name="groupBox_2">
<property name="title">
- <string>Statistics</string>
+ <string>Statistics:</string>
</property>
<layout class="QGridLayout" name="gridLayout_5">
<item row="0" column="0">

MODIFY
src/cachegraphic.cpp
src/cachegraphic.cpp
#include <QPen>
#include "processorhandler.h"
+#include "radix.h"
namespace Ripes {
@@ -25,19 +26,62 @@ void CacheGraphic::dataChanged(uint32_t address) {
const unsigned setIdx = m_cache.getAccessSetIdx();
const auto data = ProcessorHandler::get()->getMemory().readMemConst(address);
+ auto fm = QFontMetricsF(m_font);
+
+ auto& cacheline = m_cacheTextItems[lineIdx][setIdx];
// Try to locate a previously created text object for the block.
- QGraphicsSimpleTextItem* blockTextItem = m_cacheTextItems[lineIdx][setIdx][blockIdx];
+ QGraphicsSimpleTextItem* blockTextItem = cacheline.blocks[blockIdx];
if (blockTextItem == nullptr) {
blockTextItem = new QGraphicsSimpleTextItem(this);
- m_cacheTextItems[lineIdx][setIdx][blockIdx] = blockTextItem;
- }
-
- blockTextItem->setText("0x" + QString::number(data, 16));
-
- const qreal x = m_widthBeforeBlocks + blockIdx * m_blockWidth;
+ blockTextItem->setFont(m_font);
+ cacheline.blocks[blockIdx] = blockTextItem;
+ const qreal x =
+ m_widthBeforeBlocks + blockIdx * m_blockWidth + (m_blockWidth / 2 - fm.horizontalAdvance("0x00000000") / 2);
const qreal y = lineIdx * m_lineHeight + setIdx * m_setHeight;
blockTextItem->setPos(x, y);
+ }
+ const QString text = encodeRadixValue(data, Radix::Hex);
+ blockTextItem->setText(text);
+
+ // Update tag
+ QGraphicsSimpleTextItem* tagTextItem = cacheline.tag;
+ if (tagTextItem == nullptr) {
+ // Create tag
+ tagTextItem = new QGraphicsSimpleTextItem(this);
+ tagTextItem->setFont(m_font);
+ cacheline.tag = tagTextItem;
+ auto fm = QFontMetricsF(m_font);
+ const qreal x = m_widthBeforeTag + (m_tagWidth / 2 - fm.horizontalAdvance("0x00000000") / 2);
+ const qreal y = lineIdx * m_lineHeight + setIdx * m_setHeight;
+ tagTextItem->setPos(x, y);
+ }
+ const QString tagText = encodeRadixValue(m_cache.getAccessTag(), Radix::Hex);
+ tagTextItem->setText(tagText);
+
+ // Update valid & LRU text
+ // A value cannot be invalidated with the current schema (uniprocessor)
+ cacheline.valid->setText(QString::number(1));
+ if (m_cache.getReplacementPolicy() == CacheReplPlcy::LRU && m_cache.getSets() > 1) {
+ if (m_cache.getCurrentAccessLine()) {
+ auto* currentAccessLine = m_cache.getCurrentAccessLine();
+ for (const auto& way : m_cacheTextItems[m_cache.getAccessLineIdx()]) {
+ // If LRU was just initialized, the actual (software) LRU value may be very large. Mask to the number of
+ // actual LRU bits.
+ unsigned lruVal = currentAccessLine->at(way.first).lru;
+ lruVal &= generateBitmask(m_cache.getSetBits());
+ const QString lruText = QString::number(lruVal);
+ way.second.lru->setText(lruText);
+
+ // LRU text might have changed; update LRU field position to center in column
+ const qreal y = lineIdx * m_lineHeight + way.first * m_setHeight;
+ const qreal x = m_bitWidth + m_lruWidth / 2 - fm.horizontalAdvance(lruText) / 2;
+
+ way.second.lru->setPos(x, y);
+ }
+ }
+ }
+
updateHighlighting(true);
}
@@ -62,7 +106,7 @@ void CacheGraphic::updateHighlighting(bool active) {
auto* lineRectItem = m_highlightingItems.rbegin()->get();
lineRectItem->setZValue(-1);
lineRectItem->setOpacity(0.25);
- lineRectItem->setBrush(Qt::red);
+ lineRectItem->setBrush(Qt::yellow);
// Draw cache block highlighting rectangle
topLeft = QPointF(blockIdx * m_blockWidth + m_widthBeforeBlocks, 0);
@@ -75,6 +119,37 @@ void CacheGraphic::updateHighlighting(bool active) {
}
}
+void CacheGraphic::initializeControlBits() {
+ auto fm = QFontMetricsF(m_font);
+
+ for (int lineIdx = 0; lineIdx < m_cache.getLines(); lineIdx++) {
+ auto& line = m_cacheTextItems[lineIdx];
+ for (int setIdx = 0; setIdx < m_cache.getSets(); setIdx++) {
+ const qreal y = lineIdx * m_lineHeight + setIdx * m_setHeight;
+ qreal x;
+
+ // Create valid field
+ auto* validItem = new QGraphicsSimpleTextItem(this);
+ validItem->setFont(m_font);
+ validItem->setText("0");
+ x = fm.horizontalAdvance(validItem->text()) / 2;
+ validItem->setPos(x, y);
+ line[setIdx].valid = validItem;
+
+ if (m_cache.getReplacementPolicy() == CacheReplPlcy::LRU && m_cache.getSets() > 1) {
+ // Create LRU field
+ auto* lruItem = new QGraphicsSimpleTextItem(this);
+ lruItem->setFont(m_font);
+ const QString lruText = QString::number(m_cache.getSets() - 1);
+ lruItem->setText(lruText);
+ x = m_bitWidth + m_lruWidth / 2 - fm.horizontalAdvance(lruText) / 2;
+ lruItem->setPos(x, y);
+ line[setIdx].lru = lruItem;
+ }
+ }
+ }
+}
+
void CacheGraphic::cacheParametersChanged() {
prepareGeometryChange();
@@ -88,8 +163,9 @@ void CacheGraphic::cacheParametersChanged() {
auto metrics = QFontMetricsF(m_font);
m_setHeight = metrics.height();
m_lineHeight = m_setHeight * m_cache.getSets();
- m_blockWidth = metrics.horizontalAdvance("0xFFFFFFFF");
+ m_blockWidth = metrics.horizontalAdvance(" 0x00000000 ");
m_bitWidth = metrics.horizontalAdvance("00");
+ m_lruWidth = metrics.horizontalAdvance(QString::number(m_cache.getSets()) + " ");
m_cacheHeight = m_lineHeight * m_cache.getLines();
m_tagWidth = m_blockWidth;
@@ -103,6 +179,18 @@ void CacheGraphic::cacheParametersChanged() {
drawText(validBitText, 0, -metrics.height());
horizontalAdvance += m_bitWidth;
+ if (m_cache.getReplacementPolicy() == CacheReplPlcy::LRU && m_cache.getSets() > 1) {
+ // Draw LRU bit column
+ new QGraphicsLineItem(horizontalAdvance, 0, horizontalAdvance, m_cacheHeight, this);
+ new QGraphicsLineItem(m_bitWidth + m_lruWidth, 0, m_bitWidth + m_lruWidth, m_cacheHeight, this);
+ const QString LRUBitText = "LRU";
+ drawText(LRUBitText, horizontalAdvance + m_lruWidth / 2 - metrics.horizontalAdvance(LRUBitText) / 2,
+ -metrics.height());
+ horizontalAdvance += m_lruWidth;
+ }
+
+ m_widthBeforeTag = horizontalAdvance;
+
// Draw tag column
new QGraphicsLineItem(m_tagWidth + horizontalAdvance, 0, m_tagWidth + horizontalAdvance, m_cacheHeight, this);
const QString tagText = "Tag";
@@ -147,6 +235,13 @@ void CacheGraphic::cacheParametersChanged() {
const qreal x = -metrics.horizontalAdvance(text) * 1.2;
drawText(text, x, y);
}
+
+ // Draw index column text
+ const QString indexText = "Index";
+ const qreal x = -metrics.horizontalAdvance(indexText) * 1.2;
+ drawText(indexText, x, -metrics.height());
+
+ initializeControlBits();
}
} // namespace Ripes

MODIFY
src/cachegraphic.h
src/cachegraphic.h
@@ -25,10 +25,15 @@ public:
void cacheParametersChanged();
private:
+ /**
+ * @brief initializeControlBits
+ * Constructs all of the "Valid" and "LRU" text items within the cache
+ */
+ void initializeControlBits();
void updateHighlighting(bool active);
void drawText(const QString& text, qreal x, qreal y);
- QFont m_font = QFont("Roboto", 12);
+ QFont m_font = QFont("Inconsolata", 12);
CacheBase& m_cache;
std::vector<std::unique_ptr<QGraphicsRectItem>> m_highlightingItems;
@@ -42,9 +47,17 @@ private:
qreal m_tagWidth = 0;
qreal m_cacheWidth = 0;
qreal m_widthBeforeBlocks = 0;
+ qreal m_widthBeforeTag = 0;
+ qreal m_lruWidth = 0;
// Data structure modelling the cache; keeping graphics text items for each entry
- using CacheWay = std::map<unsigned, QGraphicsSimpleTextItem*>;
+ struct CacheWay {
+ std::map<unsigned, QGraphicsSimpleTextItem*> blocks;
+ QGraphicsSimpleTextItem* tag = nullptr;
+ QGraphicsSimpleTextItem* lru = nullptr;
+ QGraphicsSimpleTextItem* valid = nullptr;
+ };
+
using CacheLine = std::map<unsigned, CacheWay>;
std::map<unsigned, CacheLine> m_cacheTextItems;
};

MODIFY
src/memorytab.cpp
src/memorytab.cpp
@@ -28,7 +28,7 @@ MemoryTab::MemoryTab(QToolBar* toolbar, QWidget* parent) : RipesTab(toolbar, par
scene->addItem(cacheGraphic);
auto* accessTimer = new QTimer(this);
- accessTimer->setInterval(500);
+ accessTimer->setInterval(100);
connect(accessTimer, &QTimer::timeout, [=] {
static unsigned address = 0x0;
cacheSim->read(address);

Implement LRU cache replacement policy