Approximate Computing Approximate Computing Computation Reuse Memoization [8] [9] Auto-Memoization Processor 1 CPU ALU 1 D$1 2 D$2 MemoTbl Me

Size: px

Start display at page:

Download "Approximate Computing Approximate Computing Computation Reuse Memoization [8] [9] Auto-Memoization Processor 1 CPU ALU 1 D$1 2 D$2 MemoTbl Me"

さあしゃやたけ
5 years ago
Views:

1 Approximate Computing Approximate Computing Approximate Computing Approximate Computing MediaBench cjpeg 22.3% 29.5% 1. Approximate Computing [1] [2] Approximate Computing Auto-Memoization Processor [3] Approximate Computing Approximate Computing Approximate Computing 1 Nagoya Institute of Technology 2 Nara Institute of Science and Technology 2. Approximate Computing Raha [4] Approximate Computing Sasa [5] Shoushtari [6] Approximate Computing SRAM Approximate Computing Álvarez [7] c 2015 Information Processing Society of Japan 1

2 Approximate Computing Approximate Computing Computation Reuse Memoization [8] [9] Auto-Memoization Processor 1 CPU ALU 1 D$1 2 D$2 MemoTbl MemoTbl MemoBuf MemoTbl MemoTbl MemoBuf 1 int a = 3, b = 4, c = 8 ; 2 int c a l c ( x ) { 3 int tmp = x + 1 ; 4 tmp += a ; 5 i f ( tmp < 7) tmp += b ; 6 e l s e tmp += c ; 7 return ( tmp ) ; 8 } 9 int main ( void ) { 10 c a l c ( 2 ) ; / x = 2, a = 3, b = 4 / 11 b = 5 ; c a l c ( 2 ) ; / x = 2, a = 3, b = 5 / 12 a = 4 ; c a l c ( 2 ) ; / x = 2, a = 5, c = 8 / 13 a = 3 ; c a l c ( 2 ) ; / x = 2, a = 3, b = 5 / 14 return ( 0 ) ; 15 } 2 MemoTbl MemoTbl MemoTbl MemoTbl MemoBuf MemoBuf MemoTbl MemoBuf 1 1 FLTbl idx SP retofs Read Write Read Write addr/reg value c 2015 Information Processing Society of Japan 2

3 3 4 MemoTbl MemoTbl 2 calc 3 3 (i) (ii) (iii) i ii 3 b 12 (iii) 3 c 2 a 5 4 MemoTbl Memo- Tbl 4 FLTbl: InTbl: AddrTbl: OutTbl: FLTbl AddrTbl OutTbl RAM InTbl 3 CAM Content Addressable Memory MemoTbl FLTbl addr 5 MemoTbl InTbl FLTbl Index FLTbl idx InTbl input values 1 3 CAM InTbl parent idx AddrTbl next addr AddrTbl InTbl 1 1 AddrTbl ec flag OutTbl OutTbl idx OutTbl output addr output values OutTbl 1 next idx InTbl AddrTbl 5 5 (a) (f) 2 13 MemoTbl InTbl X 3.1 InTbl parent idx FF input values parent idx FF c 2015 Information Processing Society of Japan 3

4 6 00 (a) AddrTbl next addr 0x200 input values (b) 3 input values parent idx 00 InTbl (c) (d)(e) 03 AddrTbl ec flag AddrTbl OutTbl idx OutTbl (f) 4. Approximate Computing Approximate Computing Approximate Computing 4.1 Approximate Computing Approximate Computing 2 7 Approximate Computing Approximate Computing 32 R G B 8 RGB 4 6 0xf0f0f000 RGB 2 0xc0c0c000 MemoTbl [10] c 2015 Information Processing Society of Japan 4

5 1 #pragma approx ( img, 0 x f 0 f 0 f ) 2 int c o l 2 g r a y ( int img, f l o a t y ) { 3 int R, G, B; 4 R = img>>16; 5 G = ( img&0x f f 0 0 ) >>8; 6 B = img&0x f f ; 7 return pow (R, y )+pow (G, y )+pow (B, y ) ; 8 } 8 1 : c a l l <col2gray > 3 : 4 : <col2gray >: approx r0, 0 x f 0 f 0 f sub sp, sp, # str r1, [ sp, #8] c str r2, [ sp, #12] 10 : ret Approximate Computing #pragma approx (app input, app mask) approx app input app mask Approximate Computing 8 8 col2gray img 8 2 col2gray 1 Approximate Computing 4.3 Approximate Computing Approximate Computing 8 9 img r0 9 Approximate Computing col2gray 5 approx r0, 0xf0f0f000 col2gray MemoTbl MemoTbl MemoBuf MemoBuf approx. input approx. mask c 2015 Information Processing Society of Japan 5

6 10 MemoTbl MemoBuf MemoTbl InTbl AddrTbl 10 InTbl input values MemoTbl Approximate Computing img r0 0xf0f0f000 MemoBuf approx. input approx. mask MemoBuf 11 return MemoBuf MemoTbl MemoBuf approx. input r0 MemoBuf addr/reg 10(a) 10 addr/reg r0 approx. mask addr/reg r0 value 0xf0f0f000 10(b) 3 1 MemoBuf 64 KBytes MemoTbl CAM 128 KBytes Comparison (register and CAM) 9 cycles/32 Bytes Comparison (Cache and CAM) 10 cycles/32 Bytes Write back (MemoTbl to Reg./Cache) 1 cycle/32 Bytes D1 cache 32 KBytes line size 32 Bytes ways 4 ways latency 2 cycles miss penalty 10 cycles D2 cache 2 MBytes line size 32 Bytes ways 4 ways latency 10 cycles miss penalty 100 cycles Register windows 4 sets miss penalty 20 cycles/set MemoTbl 10(c) MemoTbl MemoTbl InTbl input values input values SPARC V8 1 SPARC64-III[11] MemoTbl InTbl CAM MOSAID DC18288[12] 32Bytes 4K 128KBytes c 2015 Information Processing Society of Japan 6

7 1 : 2 void forward Q (JSAMPLE sample... ) { 3 : 4 for ( i = 0 ; i < DCTSIZE ; i ++) { 5 q v a l = div [ i ] ; 6 temp = work [ i ] ; 7 i f ( temp < 0) { 8 temp = temp ; 9 temp += qval >>1; 10 DIVIDE BY( temp, qval ) ; 11 temp = temp ; 12 } e l s e { 13 temp += qval >>1; 14 DIVIDE BY( temp, qval ) ; 15 } 16 out [ i ] = (JCOEF) temp ; 17 } 18 : 19 } 20 : 11 1 : 2 void forward Q (JSAMPLE sample... ) { 3 : 4 for ( i = 0 ; i < DCTSIZE ; i ++) { 5 out [ i ] = q l o o p ( work [ i ], div [ i ] ) ; 6 } 7 : 8 } 9 : 10 #pragma approx ( temp, 0 x f f f f f f f 0 ) 11 JCOEF q l o o p ( temp, q v a l ) { 12 i f ( temp < 0) { 13 temp = temp ; 14 temp += qval >>1; 15 DIVIDE BY( temp, qval ) ; 16 temp = temp ; 17 } e l s e { 18 temp += qval >>1; 19 DIVIDE BY( temp, qval ) ; 20 } 21 return (JCOEF) temp ; 22 } 23 : 128KBytes CAM MediaBench cjpeg cjpeg RGB/YUV DCT Approximate Computing forward Q 7 16 q loop forward Q q loop 12 DCT temp (N) (N ) (M) (M 0) 13 : (M 2) 2 (M 4) 4 (M 6) 6 (N) 1 q loop exec read MemoTbl write MemoTbl c 2015 Information Processing Society of Japan 7

8 情報処理学会研究報告表 2 再利用率とで自動メモ化プロセッサをベースとした Approximate 評価結果:再利用率 (M) (M 0) (M 2) (M 4) (M 6) Computing 基盤を提案した MediaBench から画像圧縮 0.019% 0.029% 16.8% 24.7% 29.5% を行う cjpeg を用いて評価を行った結果非常に簡単なプログラムの書き換えにより既存の自動メモ化プロセッサと比較して最大 22.3%の命令実行サイクル数削減および最大 29.5%の再利用率向上を達成し提案手法の有効性を確認することができた今後の課題として許容できる出力の誤差率をプログラマに指定させその誤差率の範囲内で最大のパフォーマンスが得られるよう自動メモ化プロセッサが動的にマスク値を調整する機構の検討が挙げられる参考文献 [1] [2] 図 14 出力結果しオーバヘッド D$1 および D$2 は 1 次および 2 次データ [3] キャッシュミスペナルティ window はレジスタウインドウミスペナルティであるまたメモ化を行ったそれぞれの場合における関数全体の再利用率を表 2 に示す (M 2) (M 4) (M 6) の結果よりマスクする入力のビッ [4] トを増やすに連れ read および write がわずかに増加しているが exec は大きく減少しており全体の性能は向上していることがわかるまた表 2 よりマスクする入力のビットを増やすに連れ再利用率が向上していることがわかるこ [5] れらの結果から入力を部分的にマスクすることで入力の一致比較を近似化し関数単位の計算再利用率の向上および命令実行サイクル数を削減できていることがわかり提案手法による期待通りの効果が得られていることを確認できた [6] 次に入力をマスクしなかった場合の出力結果と入力をマスクした場合の出力結果を図 14 に示す図 14 より (M 2) (M 4) では入力をマスクしなかった場合の出力結果 [7] と比較してほとんど画質の低下は見られないことがわかるまた (M 6) では入力をマスクしなかった場合の出力結果と比較してわずかな画質の低下が見られるがアプリケー [8] ションによっては十分許容範囲内の画質低下に収まっている [9] と考えられる以上の結果から命令実行サイクル数の削減および再利用率の向上を達成しまた出力の精度低下が知覚的に許容できる範囲内であることを確認できた [10] 6. おわりに本稿ではこれまで我々が提案してきた自動メモ化プロセッサに Approximate Computing の考え方を適用し併せて Approximate Computing の対象とする関数や入力を指 [11] [12] Hadi, E., Adrian, S., Luis, C. and Doug, B.: Architecture Support for Disciplined Approximate Programming, Proc. 17th Int l Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS 12), pp (2012). Vaibhav, G., Debabrata, M., Anand, R. and Kaushik, R.: Low-Power Digital Signal Processing Using Approximate Adders, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 32, No. 1, pp (2013). Tsumura, T., Suzuki, I., Ikeuchi, Y., Matsuo, H., Nakashima, H. and Nakashima, Y.: Design and Evaluation of an Auto-Memoization Processor, Proc. Parallel and Distributed Computing and Networks, pp (2007). Raha, A., Venkataramani, S., Raghunathan, V. and Raghunathan, A.: Quality Conﬁgurable Reduce-andRank for Energy Eﬃcient Approximate Computing, Proc. Design, Automation & Test in Europe Conf. & Exhibition (DATE), pp (2015). Sasa, M., Michael, C., Sara, A., Qi, Z. and C., R. M.: Chisel: Reliability- and Accuracy-Aware Optimization of Approximate Computational Kernels, Proc. ACM Int l Conf. on Object Oriented Programming Systems Languages & Applications (OOPSLA 14), pp (2014). Shoushtari, M., BanaiyanMofrad, A. and Dutt, N.: Exploiting Partially-Forgetful Memories for Approximate Computing, IEEE Embedded Systems Letters, Vol. 7, No. 1, pp (2015). A lvarez, C., Corbal, J., Salamı, E. and Valero, M.: Initial Results on Fuzzy Floating Point Computation for Multimedia Processors, Computer Architecture Letters, Vol. 1, No. 1, pp. 1 4 (2002). Norvig, P.: Paradigms of Artiﬁcial Intelligence Programming, Morgan Kaufmann (1992). Huang, J. and Lilja, D. J.: Exploiting Basic Block Value Locality with Block Reuse, Proc. 5th Int l Symp. on High-Performance Computer Architecture (HPCA-5), pp (1999). 津邑公暁清水雄歩中島康彦五島正裕森眞一郎北村俊明富田眞治ステレオ画像処理を用いた曖昧再利用の評価情報処理学会論文誌コンピューティングシステム Vol. 44, No. SIG 11(ACS 3), pp (2003). HAL Computer Systems/Fujitsu: SPARC64-III User s Guide (1998). MOSAID Technologies Inc.: Feature Sheet: MOSAID Class-IC DC18288, 1.3 edition (2003). 示するためのプログラミングフレームワークを設計するこ c 2015 Information Processing Society of Japan 8

HTM RaR HTM 2. 2) 3) HTM 2 3 Yoo 4) HTM Adaptive Transaction Scheduling Akpinar 5) HTM Gaona 6) HTM 3. Read-after-Read HTM 3.1 Read-after-Read Read Wr

HTM RaR HTM 2. 2) 3) HTM 2 3 Yoo 4) HTM Adaptive Transaction Scheduling Akpinar 5) HTM Gaona 6) HTM 3. Read-after-Read HTM 3.1 Read-after-Read Read Wr 1 1, 1 1 1 1 Readafter-Read Read-after-Read 66.9% A Speed-Up Technique for Hardware Transactional Memories by Reducing Concurrency Considering Conflicting Addresses Koshiro Hashimoto, 1 Masamichi Eto,