Composable Sound Transformations of Nested Recursion and Loops
This academic research explores the composable nature of sound transformations involving nested recursion, loops, dynamic instances, iteration spaces, scheduling transformations, and more. The study delves into loop interchange, loop tiling, polyhedral model usage, traversal techniques like blocking and splicing, and the impact of various transformations on code organization. It also discusses the challenges of unifying frameworks for effective recursion interchange and fusion. Through dynamic instances and iteration space exploration, the study illustrates the significance of map iteration spaces, order code adjustment, loop reversal, and logical interchange. The content emphasizes the effective composability of transformations in loop structures and polyhedral models within complex code bases.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Composable, Sound Transformations of Nested Recursion and Loops Kirshanthan Sundararajah and Milind Kulkarni School of Electrical and Computer Engineering 1
Loops and Recursion Loop Interchange Loop Tiling for(i=0; i<N; i++){ for(j=0; j<M; j++){ a[i][j]+=2*a[i+1][j]; } } Polyhedral Model Loop Unrolling Loop Fusion for(i=0; i<N; i++) traverse(i, root); Point Blocking Traversal Splicing void traverse(int i, Node* n){ if(n==NULL) return; traverse(i, n->l); traverse(i, n->r); n->x[i] += 2*n->x[i+1]; } No unifying framework! Recursion Interchange Traversal Fusion 2
Dynamic Instances and Iteration Space j for(i=0; i<N; i++){ for(j=0; j<M; j++){ a[i][j]+=2*a[i+1][j]; } } i (0, 0):a[0][0]+=2*a[1][0] (1, 0):a[1][0]+=2*a[2][0] (0, 1):a[0][1]+=2*a[1][1] (0, 2):a[0][2]+=2*a[1][2] (0, 3):a[0][3]+=2*a[1][3] 3
Scheduling Transformation j j Map Iteration Spaces i i Change the Order Code for(i=0; i<N; i++){ for(j=0; j<M; j++){ a[i][j]+=2*a[i+1][j]; } } for(j=0; j<M; j++){ for(i=0; i<N; i++){ a[i][j]+=2*a[i+1][j]; } } Transformation 4
Composability of Transformations j j Loop Reversal i i Loop Loop Polyhedral Model Interchange Interchange j j Loop Reversal i i 5
Dynamic Instances and Iteration Space n for(i=0; i<N; i++) n = root traverse(i, root); void traverse(int i, Node* n){ if(n==NULL) return; traverse(i, n->l); traverse(i, n->r); n->x[i] += 2*n->x[i+1]; } i n = root->l n = root->r (1, root):root->x[1]+=2*root->x[2] (0, root):root->x[0]+=2*root->x[1] (0, root->l):root->l->x[0]+=2*root->l->x[1] (0, root->r):root->r->x[0]+=2*root->r->x[1] 6
Scheduling Transformation n n Map Iteration Spaces i i Change the Order void traverse(int i, Node* n){ if(n==NULL) return; traverse(i, n->l); traverse(i, n->r); for(i=0; i<N; i++) traverse(i, root); Code Transformation void traverse(int i, Node* n){ if(n==NULL) return; traverse(i, n->l); traverse(i, n->r); n->x[i] += 2*n->x[i+1]; } for(i=0; i<N; i++) n->x[i] += 2*n->x[i+1]; } 7
Scheduling Transformations Jo and Kulkarni 2012 Jo and Kulkarni 2011 Sakka et. al. 2017 Rajbhandari et. al. 2016a Sundararajah et. al. 2017 Rajbhandari et. al. 2016b 8
Composability of Transformations for(i=0; i<N; i++) for(i=0; i<N; i++) traverse(i, root); traverse(i, root); code motion void traverse(int i, Node* n){ if(n==NULL) return; traverse(i, n->l); traverse(i, n->r); n->x[i] = n->l->x[i+1]+n->r->x[i+1]; } void traverse(int i, Node* n){ if(n==NULL) return; n->x[i] = n->l->x[i+1]+n->r->x[i+1]; traverse(i, n->l); traverse(i, n->r); } Interchange Interchange void traverse(int i, Node* n){ if(n==NULL) return; traverse(i, n->l); traverse(i, n->r); for(i=0; i<N; i++) n->x[i] = n->l->x[i+1]+n->r->x[i+1]; } void traverse(int i, Node* n){ if(n==NULL) return; for(i=0; i<N; i++) n->x[i] = n->l->x[i+1]+n->r->x[i+1]; traverse(i, n->l); traverse(i, n->r); } code motion 9
Contributions A Representation of Iteration Space A Representation of Transformations A Representation of Dependences A Check for Soundness of Transformations 10
Contributions A Representation of Iteration Space A Representation of Transformations A Representation of Dependences A Check for Soundness of Transformations 11
Representation of Iteration Space i = 1, n = root->l->r void foo(int i, Node* n){ if(i>=N) return; bar(i, n); foo(i+1, n); } void bar(int i, Node* n){ if(n==NULL) return; bar(i, n->l); bar(i, n->r); n->x[i] += 2*n->x[i+1]; } } void foo(int i, Node* n){ if(i>=N) return; bar(i, n); //t1 foo(i+1, n); //r1 } void bar(int i, Node* n){ if(n==NULL) return; bar(i, n->l);//r2l bar(i, n->r);//r2r n->x[i] += 2*n->x[i+1]; //s1 [r1] [r1 t1] [r1 t1 r2l] [r1 t1 r2l r2r] [r1 t1 r2l r2r s1] Amiranoff and Cohen 2006 [r1 t1, r2l r2r s1] 12
Representation of Iteration Space void foo(int i, Node* n){ if(i>=N) return; bar(i, n); //t1 foo(i+1, n); //r1 } void bar(int i, Node* n){ if(n==NULL) return; bar(i, n->l);//r2l bar(i, n->r);//r2r n->x[i] += 2*n->x[i+1]; //s1 } Alphabet Order [t1<r1<r2l<r2r<s1] {t1,r1,r2l,r2r,s1} [t1,s1] [r1t1,s1] (i=0,n=root) (i=1,n=root) Automata String 13
Contributions A Representation of Iteration Space A Representation of Transformations A Representation of Dependences A Check for Soundness of Transformations 14
Representation of Transformation Output Alphabet {?,?,?} Input Alphabet {?,?,?} Input Iteration Space Output Iteration Space Input String Output String ?,?,? Transducer Automata Automata ?: ?,?,? Input Order [? < ? < ?] Output Order [? < ? < ?] 15
Representation of Transformation Code Motion Interchange Point Blocking (Jo et al. 2011) Traversal Splicing (Jo et al. 2012) Strip Mining Inlining 16
Contributions A Representation of Iteration Space A Representation of Transformations A Representation of Dependences A Check for Soundness of Transformations 17
Representation of Dependences j for(i=0; i<N; i++){ for(j=0; j<M; j++){ a[i][j] += 2*a[i+1][j]; } } i (0, 0): Reads{a[0][0],a[1][0]} Writes{a[0][0]} (1, 0): Reads{a[1][0],a[2][0]} Writes{a[1][0]} 18
Representation of Dependences n [t1,s1] [r1t1,s1] void foo(int i, Node* n){ if(i>=N) return; bar(i, n); //t1 foo(i+1, n); //r1 } void bar(int i, Node* n){ if(n==NULL) return; bar(i, n->l);//r2l bar(i, n->r);//r2r n->x[i] += 2*n->x[i+1];//s1 } [r1t1,s1] [r1r1t1,s1] i [r1r1t1,s1] [r1r1r1t1,s1] n = root (0, root): Reads{root->x[0],root->x[1]} Writes{root->x[0]} n = root.r n = root.l (1, root): Reads{root->x[1],root->x[2]} Writes{root->x[1]} 19
Representation of Dependences [t1,s1] [r1t1,s1] [r1t1,s1] [r1r1t1,s1] [r1r1r1t1,s1] [r1r1t1,s1] <prefix ([t1,s1] [r1t1,s1])> <[(r1)*,(r2l|r2r)*],([t1,s1],[(r1t1,s1])> Witness Tuple <prefix, (suffix1, suffix2)> 20
Contributions A Representation of Iteration Space A Representation of Transformation A Representation of Dependence A Check for Soundness of Transformations 21
Checking Soundness of Transformations For a given prefix Output Program Input Program I1 . . In I1 . . In Suffix1 Suffix1 Composed Transformation Transducer J1 . . Jm J1 . . Jm Suffix2 Suffix2 22
Evaluation Code Motion Strip Mining Interchange 136x Point Blocking (Jo et al. 2011) Inlining Strip Mining Interchange Code Motion 129x Traversal Splicing (Jo et al. 2012) Code Motion Interchange 59x New Transformation 23
Conclusion We provide a unified approach to, Represent iteration space. Represent transformations. Represent dependences. Test the validity of the sequence of transformations given the dependences. Available at https://bitbucket.org/plcl/polyrec 24
Composable, Sound Transformations of Nested Recursion and Loops Kirshanthan Sundararajah and Milind Kulkarni School of Electrical and Computer Engineering 25
