TY - GEN
T1 - Integrating loop and data optimizations for locality within a constraint network based framework
AU - Chen, Guilin
AU - Ozturk, Ozcan
AU - Kandemir, Mahmut
AU - Kolcu, Ibrahim
PY - 2005
Y1 - 2005
N2 - In the context of data-intensive embedded applications, there have been two complementary approaches to data locality problem: restructuring code and restructuring data layout. Conceivably, an integrated approach that combines these two can generate much better results than each individual approach. However, there is an inherent difficulty in optimizing both data layout and loop access pattern simultaneously under a unified setting. This difficulty occurs due to the fact that a given data structure can be accessed by different loop nests of the application, and each such loop nest can demand a different memory layout transformation for the said data structure. This results in a coupling problem, where the behaviors of two (or more) loop nests are coupled to each other as a result of data sharing between them. In this paper, we present a constraint network (CN) based formulation of the integrated loop-data optimization problem. We present two alternate solutions to the data locality problem with our CN based formulation and discuss the pros and cons of each scheme. The first solution is a pure backtracking based one, whereas the second one improves upon the first one by employing three additional optimizations, including backjumping.
AB - In the context of data-intensive embedded applications, there have been two complementary approaches to data locality problem: restructuring code and restructuring data layout. Conceivably, an integrated approach that combines these two can generate much better results than each individual approach. However, there is an inherent difficulty in optimizing both data layout and loop access pattern simultaneously under a unified setting. This difficulty occurs due to the fact that a given data structure can be accessed by different loop nests of the application, and each such loop nest can demand a different memory layout transformation for the said data structure. This results in a coupling problem, where the behaviors of two (or more) loop nests are coupled to each other as a result of data sharing between them. In this paper, we present a constraint network (CN) based formulation of the integrated loop-data optimization problem. We present two alternate solutions to the data locality problem with our CN based formulation and discuss the pros and cons of each scheme. The first solution is a pure backtracking based one, whereas the second one improves upon the first one by employing three additional optimizations, including backjumping.
UR - http://www.scopus.com/inward/record.url?scp=33751417845&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33751417845&partnerID=8YFLogxK
U2 - 10.1109/ICCAD.2005.1560078
DO - 10.1109/ICCAD.2005.1560078
M3 - Conference contribution
AN - SCOPUS:33751417845
SN - 078039254X
SN - 9780780392540
T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
SP - 279
EP - 282
BT - Proceedings of theICCAD-2005
T2 - ICCAD-2005: IEEE/ACM International Conference on Computer-Aided Design, 2005
Y2 - 6 November 2005 through 10 November 2005
ER -