mem-cache: Proactive Instruction Fetch Implementation

Ferdman, M., Kaynak, C., & Falsafi, B. (2011, December).
Proactive instruction fetch. In Proceedings of the 44th Annual IEEE/ACM
International Symposium on Microarchitecture (pp. 152-162). ACM.

Change-Id: I38c3ab30a94ab279f03e3d5936ce8ed118310c0e
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/16968
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Reviewed-by: Daniel Carvalho <odanrc@yahoo.com.br>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>

1 files changed, 191 insertions, 0 deletions

diff --git a/src/mem/cache/prefetch/pif.hh b/src/mem/cache/prefetch/pif.hh
new file mode 100644
index 000000000..6516b2c6a
--- /dev/null
+++ b/src/mem/cache/prefetch/pif.hh
@@ -0,0 +1,191 @@
+/**
+ * Copyright (c) 2019 Metempsy Technology Consulting
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Authors: Ivan Pizarro
+ */
+
+/** Implementation of the 'Proactive Instruction Fetch' prefetcher
+ *  Reference:
+ *    Ferdman, M., Kaynak, C., & Falsafi, B. (2011, December).
+ *    Proactive instruction fetch.
+ *    In Proceedings of the 44th Annual IEEE/ACM International Symposium
+ *    on Microarchitecture (pp. 152-162). ACM.
+ */
+
+#ifndef __MEM_CACHE_PREFETCH_PIF_HH__
+#define __MEM_CACHE_PREFETCH_PIF_HH__
+
+#include <deque>
+#include <vector>
+
+#include "mem/cache/prefetch/associative_set.hh"
+#include "mem/cache/prefetch/queued.hh"
+
+struct PIFPrefetcherParams;
+
+class PIFPrefetcher : public QueuedPrefetcher
+{
+    private:
+        /** Number of preceding and subsequent spatial addresses to compact */
+        const unsigned int precSize;
+        const unsigned int succSize;
+        /** Number of entries used for the temporal compactor */
+        const unsigned int maxCompactorEntries;
+        /** Max number of entries to be used in the Stream Address Buffer */
+        const unsigned int maxStreamAddressBufferEntries;
+
+        /**
+         * The compactor tracks retired instructions addresses, leveraging the
+         * spatial and temporal locality among instructions for compaction. It
+         *comprises the spatial and temporal compaction mechanisms.
+         *
+         * Taking advantage of the spatial locality across instruction blocks,
+         * the spatial compactor combines instruction-block addresses that fall
+         * within a 'spatial region', a group of adjacent instruction blocks.
+         * When an instruction outside the current spatial region retires, the
+         * existing spatial region is sent to the temporal compactor.
+         *
+         * The temporal compactor tracks a small number of the
+         * most-recently-observed spatial region records.
+         */
+        struct CompactorEntry {
+            Addr trigger;
+            std::vector<bool> prec;
+            std::vector<bool> succ;
+            CompactorEntry() {}
+            CompactorEntry(Addr, unsigned int, unsigned int);
+
+            /**
+             * Checks if a given address is in the same defined spatial region
+             * as the compactor entry.
+             * @param addr Address to check if it's inside the spatial region
+             * @param log_blk_distance log_2(block size of the cache)
+             * @param update if true, set the corresponding succ/prec entry
+             * @return TRUE if they are in the same spatial region, FALSE
+             *   otherwise
+             */
+            bool inSameSpatialRegion(Addr addr, unsigned int log_blk_size,
+                                     bool update);
+            /**
+             * Checks if the provided address is contained in this spatial
+             * region and if its corresponding bit vector entry is set
+             * @param target address to check
+             * @param log_blk_distance log_2(block size of the cache)
+             * @return TRUE if target has its bit set
+             */
+            bool hasAddress(Addr target, unsigned int log_blk_size) const;
+
+            /**
+             * Fills the provided vector with the predicted addresses using the
+             * recorded bit vectors of the entry
+             * @param log_blk_distance log_2(block size of the cache)
+             * @param addresses reference to a vector to add the generated
+             * addresses
+             */
+            void getPredictedAddresses(unsigned int log_blk_size,
+                    std::vector<AddrPriority> &addresses) const;
+          private:
+            /**
+             * Computes the distance, in cache blocks, from an address to the
+             * trigger of the entry.
+             * @param addr address to compute the distance from the trigger
+             * @param log_blk_distance log_2(block size of the cache)
+             * @result distance in cache blocks from the address to the trigger
+             */
+            unsigned int distanceFromTrigger(Addr addr,
+                                             unsigned int log_blk_size) const;
+        };
+
+        CompactorEntry spatialCompactor;
+        std::deque<CompactorEntry> temporalCompactor;
+
+        /**
+         * History buffer is a circular buffer that stores the sequence of
+         * retired instructions in FIFO order.
+         */
+        std::vector<CompactorEntry> historyBuffer;
+        unsigned int historyBufferTail;
+
+        struct IndexEntry : public TaggedEntry
+        {
+            unsigned int historyIndex;
+        };
+        /**
+         * The index table is a small cache-like structure that facilitates
+         * fast search of the history buffer.
+         */
+        AssociativeSet<IndexEntry> index;
+
+        /**
+         * A Stream Address Buffer (SAB) tracks a window of consecutive
+         * spatial regions. The SAB mantains a pointer to the sequence in the
+         * history buffer, initiallly set to the pointer taken from the index
+         * table
+         */
+        std::deque<CompactorEntry*> streamAddressBuffer;
+
+        /**
+         * Updates the prefetcher structures upon an instruction retired
+         * @param pc PC of the instruction being retired
+         */
+        void notifyRetiredInst(const Addr pc);
+
+        /**
+         * Probe Listener to handle probe events from the CPU
+         */
+        class PrefetchListenerPC : public ProbeListenerArgBase<Addr>
+        {
+          public:
+            PrefetchListenerPC(PIFPrefetcher &_parent, ProbeManager *pm,
+                             const std::string &name)
+                : ProbeListenerArgBase(pm, name),
+                  parent(_parent) {}
+            void notify(const Addr& pc) override;
+          protected:
+            PIFPrefetcher &parent;
+        };
+
+        /** Array of probe listeners */
+        std::vector<PrefetchListenerPC *> listenersPC;
+
+
+    public:
+        PIFPrefetcher(const PIFPrefetcherParams *p);
+        ~PIFPrefetcher() {}
+
+        void calculatePrefetch(const PrefetchInfo &pfi,
+                               std::vector<AddrPriority> &addresses);
+
+        /**
+         * Add a SimObject and a probe name to monitor the retired instructions
+         * @param obj The SimObject pointer to listen from
+         * @param name The probe name
+         */
+        void addEventProbeRetiredInsts(SimObject *obj, const char *name);
+};
+
+#endif // __MEM_CACHE_PREFETCH_PIF_HH__