TY - GEN

T1 - Reinforcement learning for automated performance tuning

T2 - 2008 IEEE International Conference on Cluster Computing, ICCC 2008

AU - Armstrong, Warren

AU - Rendell, Alistair P.

PY - 2008/1/1

Y1 - 2008/1/1

N2 - The field of reinforcement learning has developed techniques for choosing beneficial actions within a dynamic environment. Such techniques learn from experience and do not require teaching. This paper explores how reinforcement learning techniques might be used to determine efficient storage formats for sparse matrices. Three different storage formats are considered: coordinate, compressed sparse row, and blocked compressed sparse row. Which format performs best depends heavily on the nature of the matrix and the computer system being used. To test the above a program has been written to generate a series of sparse matrices, where any given matrix performs optimally using one of the three different storage types. For each matrix several sparse matrix vector products are performed. The goal of the learning agent is to predict the optimal sparse matrix storage format for that matrix. The proposed agent uses five attributes of the sparse matrix: the number of rows, the number of columns, the number of non-zero elements, the standard deviation of non-zeroes per row and the mean number of neighbours. The agent is characterized by two parameters: an exploration rate and a parameter that determines how the state space is partitioned. The ability of the agent to successfully predict the optimal storage format is analyzed for a series of 1,000 automatically generated test matrices.

AB - The field of reinforcement learning has developed techniques for choosing beneficial actions within a dynamic environment. Such techniques learn from experience and do not require teaching. This paper explores how reinforcement learning techniques might be used to determine efficient storage formats for sparse matrices. Three different storage formats are considered: coordinate, compressed sparse row, and blocked compressed sparse row. Which format performs best depends heavily on the nature of the matrix and the computer system being used. To test the above a program has been written to generate a series of sparse matrices, where any given matrix performs optimally using one of the three different storage types. For each matrix several sparse matrix vector products are performed. The goal of the learning agent is to predict the optimal sparse matrix storage format for that matrix. The proposed agent uses five attributes of the sparse matrix: the number of rows, the number of columns, the number of non-zero elements, the standard deviation of non-zeroes per row and the mean number of neighbours. The agent is characterized by two parameters: an exploration rate and a parameter that determines how the state space is partitioned. The ability of the agent to successfully predict the optimal storage format is analyzed for a series of 1,000 automatically generated test matrices.

KW - sparse matricies

KW - learning

KW - tuning

KW - arrays

UR - http://www.scopus.com/inward/record.url?scp=57949097109&partnerID=8YFLogxK

U2 - 10.1109/CLUSTR.2008.4663802

DO - 10.1109/CLUSTR.2008.4663802

M3 - Conference contribution

AN - SCOPUS:57949097109

SN - 9781424426409

T3 - Proceedings - IEEE International Conference on Cluster Computing, ICCC

SP - 411

EP - 420

BT - Proceedings of the 2008 IEEE International Conference on Cluster Computing, CCGRID 2008

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 29 September 2008 through 1 October 2008

ER -