SniperのPrefetcherのアルゴリズムについて調査する

SniperのPrefetcherについて調査する。

SniperのPrefetcherは、ベースになるPrefetcherクラスとそれを派生する形で各種プリフェッチャが定義されている。

• sniper/common/core/memory_subsystem/parametric_dram_directory_msi/prefetcher.h

class Prefetcher
{
   public:
      static Prefetcher* createPrefetcher(String type, String configName, core_id_t core_id, UInt32 shared_cores);

      virtual std::vector<IntPtr> getNextAddress(IntPtr current_address, core_id_t core_id) = 0;
};

基底クラスで定義しなければならないのは、createPrefetcher()とgetNextAdderss()関数のみだ。

createPrefetcher()は、パラメータに応じてクラスをインスタンス化する。新しいプリフェッチャを定義する場合はここにパラメータを追加することになると思う。

• sniper/common/core/memory_subsystem/parametric_dram_directory_msi/prefetcher.cc

Prefetcher* Prefetcher::createPrefetcher(String type, String configName, core_id_t core_id, UInt32 shared_cores)
{
   if (type == "none")
      return NULL;
   else if (type == "simple")
      return new SimplePrefetcher(configName, core_id, shared_cores);
   else if (type == "ghb")
      return new GhbPrefetcher(configName, core_id);
   else if (type == "a53prefetcher")
       return new A53Prefetcher(configName, core_id);

   LOG_PRINT_ERROR("Invalid prefetcher type %s", type.c_str());
}

getNextAddress()関数は、現在アクセスされたアドレスから、次にフェッチすべきアドレスの一覧を取得する。

例えば、sniper/common/core/memory_subsystem/parametric_dram_directory_msi/simple_prefetcher.ccを見てみる。

class SimplePrefetcher : public Prefetcher
{
   public:
      SimplePrefetcher(String configName, core_id_t core_id, UInt32 shared_cores);
      virtual std::vector<IntPtr> getNextAddress(IntPtr current_address, core_id_t core_id);
/* ... 途中省略 ... */
            std::vector<std::vector<IntPtr> > m_prev_address;
};

おそらく、重要なのはm_prev_addressで、これはベクトルとして定義されている。

まず、current_addressと、これまでに記録されたすべてのメモリアクセスの記録m_prev_addressとの距離が最も短いアドレスを抽出する。

m_prev_addressはこれまでのメモリ・アクセスを記録しており、サイズはn_flowsだけスロットがある。

std::vector<IntPtr>
SimplePrefetcher::getNextAddress(IntPtr current_address, core_id_t _core_id)
{
   std::vector<IntPtr> &prev_address = m_prev_address.at(flows_per_core ? _core_id - core_id : 0);

   UInt32 n_flow = n_flow_next;
   IntPtr min_dist = PAGE_SIZE;
   n_flow_next = (n_flow_next + 1) % n_flows; // Round robin replacement

     // リスト内の最も近しいアドレスを検索する
   for(UInt32 i = 0; i < n_flows; ++i)
   {
      IntPtr dist = abs(static_cast<SInt64>(current_address) - static_cast<SInt64>(prev_address[i]));
      if (dist < min_dist)
      {
         n_flow = i;
         min_dist = dist;
      }
   }

   // 現在、n_flowはこれまでにアクセスした最も近いマッチしたフローを示している。
     // あるいは、マッチしない場合アドレスをリプレースする一つのスロットを選択したことになっている。

     // プリフェッチのストライドを決める
   IntPtr stride = current_address - prev_address[n_flow];

     // アドレスの記録を更新する
   prev_address[n_flow] = current_address;

次に、プリフェッチすべきアドレスの一覧を作成する。これは上記のストライドを使ってアドレスを計算する。ページの境界を跨ぐ場合はストップする。

  std::vector<IntPtr> addresses;
   if (stride != 0)
   {
      for(unsigned int i = 0; i < num_prefetches; ++i)
      {
         IntPtr prefetch_address = current_address + i * stride;
         // But stay within the page if requested
         if (!stop_at_page || ((prefetch_address & PAGE_MASK) == (current_address & PAGE_MASK)))
            addresses.push_back(prefetch_address);
      }
   }

このgetNextAddress()はキャッシュ・コントローラ上で呼び出される。CacheCntlr::trainPrefetcher()内で呼び出されているようだ。CacheCtrlr内でのプリフェッチャの挙動を追いかけていこう。

/*****************************************************************************
 * operations called by core on first-level cache
 *****************************************************************************/

HitWhere::where_t
CacheCntlr::processMemOpFromCore(
      Core::lock_signal_t lock_signal,
      Core::mem_op_t mem_op_type,
      IntPtr ca_address, UInt32 offset,
      Byte* data_buf, UInt32 data_length,
      bool modeled,
      bool count)
/* ... 途中省略 ... */
   if (modeled && m_master->m_prefetcher)
   {
       trainPrefetcher(ca_address, cache_hit, prefetch_hit, false, t_start);
      if (m_enable_log) {
         fprintf(stderr, "%s processMemOpFromCore::trainPrefetcher() finished\n", m_configName.c_str());
      }
   }

   // Call Prefetch on next-level caches (but not for atomic instructions as that causes a locking mess)
   if (lock_signal != Core::LOCK && modeled)
   {
      if (m_enable_log) {
         fprintf(stderr, "%s processMemOpFromCore::Prefetch(t_start) call\n", m_configName.c_str());
      }
      Prefetch(t_start);
   }

キャッシュ・アクセス中に一通りのアクセスを行った後、プリフェッチャが存在していれば：

1. trainPrefetcher()を呼び出す
2. Prefetch()を実行する

まず、trainPrefetcher()は先ほどのgetNextAddress()で作り出したアドレスの一覧から、PREFETCH_MAX_QUEUE_LENGTH（デフォルトは32）だけアドレスをプリフェッチ・キューに挿入し直す。

このとき、m_master->m_prefetch_nextには、次にプリフェッチすべき時間を少し遅延させる。これはつまりメモリ・アクセスがあった直後にプリフェッチを実行せず、少し遅らせるということか？

void
CacheCntlr::trainPrefetcher(IntPtr address, bool cache_hit, bool prefetch_hit, bool prefetch_own, SubsecondTime t_issue)
{
   ScopedLock sl(getLock());

   std::vector<IntPtr> prefetchList;

   bool prefetcherTrained;

   // Train the prefetcher always or only on misses on lines that are not being brought by the prefetcher (load or store miss)
   if (m_train_prefetcher_on_hit || (!prefetch_own && !cache_hit)) {
      prefetchList = m_master->m_prefetcher->getNextAddress(address, m_core_id);
      prefetcherTrained = true;
   }
   else prefetcherTrained = false;

   // Only do prefetches on misses, or on hits to lines previously brought in by the prefetcher (if enabled)
   if (prefetcherTrained && (!cache_hit || (m_prefetch_on_prefetch_hit && prefetch_hit)))
   {
      m_master->m_prefetch_list.clear();

      // Just talked to the next-level cache, wait a bit before we start to prefetch if enabled
      m_master->m_prefetch_next = m_prefetch_delay ? t_issue + PREFETCH_INTERVAL:t_issue;

      for(std::vector<IntPtr>::iterator it = prefetchList.begin(); it != prefetchList.end(); ++it)
      {
         // Keep at most PREFETCH_MAX_QUEUE_LENGTH entries in the prefetch queue
         if (m_master->m_prefetch_list.size() > PREFETCH_MAX_QUEUE_LENGTH)
            break;
         if (!operationPermissibleinCache(*it, Core::READ)) {
            m_master->m_prefetch_list.push_back(*it);
         }
      }
   }
}

次にPrefetch()関数だ。これは先ほどのプリフェッチ・キューからアドレスを1つ取り出してアクセスを行う。

void
CacheCntlr::Prefetch(SubsecondTime t_now)
{
   IntPtr address_to_prefetch = INVALID_ADDRESS;
   //IntPtr addresses_to_prefetch[32];
   {
      ScopedLock sl(getLock());

      if (m_master->m_prefetch_next <= t_now)
      {
         while(!m_master->m_prefetch_list.empty())
         {
            IntPtr address = m_master->m_prefetch_list.front();
            m_master->m_prefetch_list.pop_front();

            // Check address again, maybe some other core already brought it into the cache
            if (!operationPermissibleinCache(address, Core::READ))
            {
               //addresses_to_prefetch[count++] = address;
               address_to_prefetch = address;
               // Do at most one prefetch now, save the rest for a future call
               break;
            }
         }
      }
   }

   if (address_to_prefetch != INVALID_ADDRESS)
   {
      doPrefetch(address_to_prefetch, m_master->m_prefetch_next);
      atomic_add_subsecondtime(m_master->m_prefetch_next, PREFETCH_INTERVAL);
   }

   // In case the next-level cache has a prefetcher, run it
   if (m_next_cache_cntlr)
      m_next_cache_cntlr->Prefetch(t_now);
}

void
CacheCntlr::doPrefetch(IntPtr prefetch_address, SubsecondTime t_start)
{
   ++stats.prefetches;
   acquireStackLock(prefetch_address);
   MYLOG("prefetching %lx", prefetch_address);
   SubsecondTime t_before = getShmemPerfModel()->getElapsedTime(ShmemPerfModel::_USER_THREAD);
   getShmemPerfModel()->setElapsedTime(ShmemPerfModel::_USER_THREAD, t_start); // Start the prefetch at the same time as the original miss
   HitWhere::where_t hit_where = processShmemReqFromPrevCache(this, Core::READ, prefetch_address, true, true, Prefetch::OWN, t_start, false);

   if (hit_where == HitWhere::MISS)
   {
      /* last level miss, a message has been sent. */

      releaseStackLock(prefetch_address);
      waitForNetworkThread();
      wakeUpNetworkThread();

      hit_where = processShmemReqFromPrevCache(this, Core::READ, prefetch_address, false, false, Prefetch::OWN, t_start, false);

      LOG_ASSERT_ERROR(hit_where != HitWhere::MISS, "Line was not there after prefetch");
   }

   getShmemPerfModel()->setElapsedTime(ShmemPerfModel::_USER_THREAD, t_before); // Ignore changes to time made by the prefetch call
   releaseStackLock(prefetch_address);
}