| Both sides previous revision
Previous revision
Next revision
|
Previous revision
|
tutorial_forward_substitution [2024/09/24 13:29]
sanjay [How to really thoroughly check the very first equational program] |
tutorial_forward_substitution [2024/09/26 07:56] (current)
sanjay [How to check more thoroughly] |
| | =====Getting started with Alpha and AlphaZ===== |
| | |
| | Alpha is a polyhedral equational language, and AlphaZ is its "IDE:" tools to read, write, edit, and analyze Alpha Programs, and also to compile them to executable code. |
| | |
| | =====Your first Alpha program (not hello world)===== |
| | |
| In this tutorial, which complements Section 1.1 from [[https://www.cs.colostate.edu/~cs560/Fall2015/Lectures/foundations1.pdf | Foundations 1]], we will walk through a simple Alpha program that solves the equation Lx=b where L is a lower triangular matrix with unit diagonals, b is a known vector and x is the unknown vector, using the forward substitution algorithm. With a little bit of algebraic reasoning, we derived a mathematical identity with x on the left hand side LHS. We now want to write it as an equational program in Alpha. You will see that it is surprisingly simple. | In this tutorial, which complements Section 1.1 from [[https://www.cs.colostate.edu/~cs560/Fall2015/Lectures/foundations1.pdf | Foundations 1]], we will walk through a simple Alpha program that solves the equation Lx=b where L is a lower triangular matrix with unit diagonals, b is a known vector and x is the unknown vector, using the forward substitution algorithm. With a little bit of algebraic reasoning, we derived a mathematical identity with x on the left hand side LHS. We now want to write it as an equational program in Alpha. You will see that it is surprisingly simple. |
| |
| =====Writing Alpha===== | |
| ====Step 1: Affine System and Parameters ==== | ====Step 1: Affine System and Parameters ==== |
| Let's start from an empty alpha file “forward_sub".ab, in which with “FS" is the name of the system, and a positive integer N as its parameter. | Let's start from an empty alpha file “forward_sub".ab, in which with “FS" is the name of the system, and a positive integer N as its parameter. |
| |
| ==make verify== | ==make verify== |
| This only becomes useful if you have a known, correct implementation of the function. For this first tutorial, it does not make sense (it ends up comparing the outputs of two identical functions). Later, when you produce different versions using scheduling directives, it becomes useful to validate the correctness agains the original equations, | This only becomes useful if you have a known, correct implementation of the function. For this first tutorial, it does not make sense (it ends up comparing the outputs of two identical functions). Later, when you produce different versions using scheduling directives, it becomes useful to validate the correctness against the original equations, |
| Compiles the code with another code named ''xxx_verify.c'' that defines a function ''xxx_verify'' (''xxx'' is the system name). | Compiles the code with another code named ''xxx_verify.c'' that defines another function with the same signature, ''xxx_verify'' (''xxx'' is the system name). |
| Users can provide different programs as ''xxx_verify'' to compare outputs. | Users can provide different programs as ''xxx_verify'' to compare outputs. |
| ==make verify-rand== | ==make verify-rand== |
| </sxh> | </sxh> |
| |
| Actually the above equation has to be corrected, because the (unit) diagonal elements of L are not explicitly stored. You may want to define/use an auxiliary variables like bp. Also, there is no ''abs'' operator in Alpha. But you can make user-defined operators by declaring them as an external function in the header (the code generator will produce a ''.h'' file, in which you will have to provide its implementation). Another (cute) way is to use the fact that ''abs(x)'' equals ''max(x, -x)'' | Note how we account for the (unit) diagonal elements of L (which are not explicitly part of the array L. |
| |
| <sxh alphabets; gutter:true> | <sxh alphabets; gutter:true> |
| </sxh> | </sxh> |
| |
| But how to provide sufficiently large number of (random) inputs to the code if we don't use the verify option? The answer is to create a sufficiently large file of rand inputs, and then use file redirection in linux to feed this file to ''xxx_check'' (make sure that the boolean output is either first or last, or even the only one). | But how to provide sufficiently large number of (random) inputs to the code if we don't use the verify option? The answer is to create a sufficiently large file of random inputs, and then use file redirection in linux to feed this file to ''xxx_check'' (make sure that the boolean output is either first or last, or even the only one). |
| |
| |
| |
