Diary/2008-9-8

C++ Annotations

NetBSDのMLでC++ Annotationsが紹介されていた．
ちょっとC++とか覚えてみようかなあ．

Maps: A Compiler-Managed Memory System for Raw Machines ^[1]

[論文読み]
Rawプロセッサのためのデータ割り当てを
コンパイル時の静的な手法と，実行時の動的な手法を組み合わせて実現する．
「2. Background」では，Raw Processorのタイル間データ転送の手法や
オーバヘッドについての計測結果が示されている．
プログラムのポインタ解析には，
SPAN(a state-of-the-art pointer analysis package)を利用．

静的な手法

• Equivalence class unification
  • ECU promotes all memory references in a single alias equivalence class by placing all objects corresponding to that class on the same tile.
  • For structs, SPAN differentiates between accesses to different fields, so that fields of a struct can be in different alias equivalence classes and distributed across the tiles.
• Modulo unrolling
  • the major limitation of ECU is that an array is treated as a single object belonging to a single equivalence class.

動的な手法

「4.3 Uses for dynamic accesses」で問題提起
モジュロスケジューリングは過剰な展開を引き起こすことも
A[B[i]]みたいなのを分割するとロクなことにならない．
static synchronizationとsoftware serial orderingで実現

• Enforcing dynamic dependences
  • A static-dynamic dependence can be enforced through explicit synchronization between the static reference and either the initiation or the completion of the dynamic reference.
  • software serial ordering to efficiently ensure dynamic-dynamic dependences.
    • it leverages the in-order delivery of messages on the dynamic network between any source-destination pair of tiles.
• Dynamic optimization
  • Epoch = all the dynamic memory accesses to an alias equivalence class in a region of the program are independent from each other.
    • without serialization
    • by placing memory barriers before and after the region
• Update = memory handlers which implement simple read/modify/write operations on memory elements.
  • the compiler migrates simple read/modify/wirte memory operations from the main program to the memory handlers.
    • a program can dispatch an update just like a store and then proceed without waiting for its completion.
    • an update collapses two expensive and serial dynamic memory operations, a load and a store, into one.
    • the associativity and commutativity of the updates effectively removes dependences between different updates.

関連研究

Software DSMの既存研究と比較

• Shasta: A Low Overhead, Software-Only Approach for Supporting Fine-Grain Shared Memory
• An Integrated Compile-Time/Run-Time Software Distributed Shared Memory System

これらと比較して

• Maps turns sequential access from a single memory image into decentralized accesses across Raw tiles

A Dynamic Code Placement Technique for Scratchpad Memory Using Postpass Optimization ^[2]

[論文読み]
プログラムコードをSPMにどう格納するか．速度と電力の評価．

• バイナリイメージを解析してcodeをSPMにいれる
• ループを展開する(function abstractionを使う)
• ILP問題に落としこんで要求されたページに対するコードマッピングを取り扱う

Dynamic Overlay of Scratchpad Memory for Energy Minimization^[3]

[論文読み]

• A Dynamic Code Placement Technique for Scratchpad Memory Using Postpass Optimizationで，様々なmemory objectsでSPMを共有する手法として引用されている．<= ソースコードが必要なのでよくないと言われている．
• we present a profile based approach which on the basis of live ranges of both variables and code segments, replenishes the contents of the SPM.
• ILPを使った静的解析．

Memory Objects

scratchpad overlayの候補

• Global variables(both scalar and non-scalar)
• Non-scalar local variables
  • they consume a space on the stack
  • they are generally not assigned to the register file.
• Code segments called traces
  • identified using the Trace Generation technique

Liveness Analysis

CFGを作ってdef-mod-use解析をする

Memory Assignment Problem

• MOに{DEF, MOD, USE, CONT}なるAttrib_{STATIC}を定義
  • DEF > MOD > USE > CONTな優先順位
• edgeに{LOAD, STORE}なるAttrib_{SPILL}を定義
• ILPで定式化，解く．

Onchip Address Assignment Problem

• address assignment problemをILPで定式化

Assigning Program and Data Objects to Scratchpad for Energy Reduction^[4]

[論文読み]

• Dynamic Overlay of Scratchpad Memory for Energy MinimizationにSPMに対して静的に命令とデーを割り当てる手法として引用されている．

Data Partitioning for Maximal Scratchpad Usage^[5]

[論文読み]

• Dynamic Overlay of Scratchpad Memory for Energy MinimizationにSPMに対して静的に命令とデーを割り当てる手法として引用されている．
• Assigning Program and Data Objects to Scratchpad for Energy Reductionに対し，配列が一つのオブジェクトとして割り当てられるのを解決するために分割する手法を提案．

文献リスト

• [1]http://doi.acm.org/10.1145/307338.300980
• [2]http://doi.acm.org/10.1145/1176760.1176788
• [3]http://doi.acm.org/10.1145/1016720.1016748
• [4]http://portal.acm.org/citation.cfm?id=874376
• [5]http://doi.acm.org/10.1145/1119772.1119788