Home Tutorial Example Top

Algorithms in *AIDA: Explanation by Examples

An algorithm is a precise plan of actions specifying how to solve a problem. Usually such a plan is based on a finite set of instructions and constructs defining a partial order of the instruction execution. We consider algorithms as activities in 4-dimential space-time. For developing an algorithm we define some space of activity (space data structures including their shapes, sizes and possible combinations), as well as attributes (parameters) representing the space node states. We also define traversal fronts of activity within the space data structures, concrete computational operations related to the traversal fronts, and input-output operations representing initial and final states of the space data structures.

Problems

  1. Adjustment of physical field attributes
  2. Jacobi relaxation algorithm for Laplace's equation
  3. Sparse matrix-vector multiplication
 

Adjustment of physical field attributes

Example 1.1

Assume we have a physical field represented by an integer attribute on a 2-D grid. The task is to find all nodes with negative values of the attribute and replace these values by "0."

The Main view of *AIDA program for this example is presented by Fig. 2.1. The first row shows the declaration of a 2-D structure and variable A (in fact, a 2-D array) which integer elements are associated to all nodes of the structure; a micro-icon (generic a-picture) to the left of A specifies the integer type of the elements.

Fig. 2.1. *AIDA program for Example 1.1

The second and fourth rows show input and output operations. Each of these rows includes an a-picture of a scene, a triple-circle micro-icon (also a generic a-picture) of a collective operation, and an expression of the operation. An a-picture of a scene, if we look at its Dynamics Details view, usually presents a series of steps where some highlighting nodes demonstrate various computational activities on a structure. In our example, the series includes only one step where all nodes of the 2-D structure are flashed by the same red color. The "caption" at the bottom of the a-picture requires specifying only one type of computational activity related to this color. Usually, this means that such activity is performed in parallel on all highlighting nodes. However, in our example, a collective activity (operation) is used. A micro-icon of a collective operation is next to the a-picture. It means that data, in some indivisibility manner, are taken from all highlighting nodes, processed and returned within the operation which on default knows what and where should be done. In the second row, it is an input operation that reads data from a file and distributes them among elements of A on the highlighting nodes. In the fourth row, it is an output operation that displays values of A at monitor through the default use of a "value-to-color" function. Some details of this function are available from environment settings or annotations.

The third row defines the basic computation by an a-picture of a scene, a micro-icon of an individual operation, and an expression of the operation. The a-picture presents a series of steps of a 2-D structure traversal scheme in "top-down, row-to-row, left-to-right" manner. At each step, only one node is flashed. In this node, the operation based on selecting maximum of two arguments is executed.

To simplify understanding this *AIDA program, the text of Example 1.1 can be attached to the Main view as an annotation to be available on demand.

 

Example 1.2

Assume we have a physical field represented by a real attribute on a 2-D grid but this field has an internal sub-field of "no activity zone." The task is like in the previous example to find all available nodes with negative values of the attribute and replace these values by "0."

Fig. 2.2. *AIDA program for Example 1.2

In this example, a micro-icon for the declaration of real type elements, icons for specifying masks ("no activity zone") and "if-then" constructs, as well as a function generating random number in the (-5.0,5.0) interval are shown. The mask area is defined by values of (r1,c1) and (r2,c2) coordinates, and the "if-then" construct is disclosed through "condition" and "operation expression" related to rhombus and wave micro-icons. The colored vertical lanes are used to enhance the visual perception of the condition and operation expressions (especially, for cases when they are rather complex). Numbers on these lanes (as well as under highlighted circles of the traversal scheme activity) are just labels to distinguish colors; this is important for people who are not good in color recognition, etc.

In this example, the mask has a name of obst (obstacle). It can be put in a library and called by the name. In such a case, coordinates (r1,c1) and (r2,c2) can be covered and shown only on demand.

 

Example 1.3

Assume that the task of Example 1.1 is to find all nodes with negative values of the real attribute, replace these values by average values of neighboring nodes, and to keep the initial version of all values.

In this example, the traversal scheme of computation related to the third row skips boundary nodes. This is pointed by a mask icon. It does not depend on changeable parameters and can be used without the declaration in advance. Short arrow bars around the red circle point out that values of variable A are not taken from a node highlighted by the traversal scheme, but from a node of a corresponding neighborhood (of right, top, left, and bottom directions).

Fig. 2.3. *AIDA program for Example 1.3

To see more complex examples, please go to these links:

Jacobi relaxation algorithm for Laplace' s equation

Example 2.1

Assume we solve a Dirichlet problem for Laplace's equation in the interior of a given 2-D region that takes prescribed values on the boundary of the region. In addition, assume that Jacobi relaxation algorithm is applied.

Through this example, the explanation of the observer node structure and corresponding variables, as well as new traversal schemes, computation on boundaries and formula patterns are provided. In addition, clarity annotations based on Algorithmic Dynamics view are also introduced.

Laplace's equation 2A/∂x2 + ∂2A/∂y2 = 0 on a 2-D grid of N × M size with some values on the boundary of the domain is solved by the Jacobi relaxation algorithm that is by an iteration process where at each step new values of A in internal points of the grid are calculated based on values of the previous step in the neighboring points (defined by a finite difference scheme). Assume that variable B is used for keeping the new iteration values and variables e and I are for checking the process of convergence. Variables A, B and I are attached ("associated") to the 2-D structure specialized on presenting computation distributed in space and e is attached to a special one-node structure specialized for presenting centralized computation. This node is also called "an observer node" where indivisible operations are performed. These operations can read variable values from space structures, but cannot change them. Only variables associated with the observer node can be changed by the operations.

The picture below (Fig. 2.4) is a Main view CyberFrame defining the algorithm. The first row in the frame is the declaration of the 2-D structure and one-node structure, as well as variables (including their types: double-real for A, B, and e; integer for I) associated to the structures. The computation includes two scenes for internal node values input and boundary values initialization, and one scene for a main part of the algorithm and results visualization. Each scene has its own a-picture with a "caption" pointing operations which should be defined within the scene computation. The scene a-pictures are depicted by the left column of the frame and request (from top-to-bottom) specifying 1, 1, and 4 operations, respectively. The operations are defined by the expressions presented to the right of the a-pictures.

Jacobi Relaxation Algorithm

Fig. 2.4. Main view of *AIDA program of the Jacobi relaxation algorithm for Laplace's equation

The second scene is scanning boundary nodes of the 2-D grid and performing in the node of the visit the rightly defined formula (a highlighted node with vertical/horizontal line means a number of row/column where the node of the visit is located). Though this scene a-picture is intuitively understandable, the user can request its semantics at any moment, as shown by Fig.2.5. The similar case with the third scene a-picture is provided by Fig.2.6. In fact, in all these cases, frames of Algorithmic Dynamics view are shown. The embedded clarity support is applicable not only to scene a-pictures, but also to generic and compound pictures, including micro-icons related to the variable declaration. Fig.2.7 depicts examples of a physical meaning and units-of-measure clarifications for variable A (representing "Temperature" in Kelvin degrees), as well as unfolded forms of neighborhood where computational activity is performed.

Jacobi Relaxation Algorithm

Fig. 2.5. Explanation of the second scene a-picture by a series of traversal CyberFrames

Jacobi Relaxation Algorithm

Fig. 2.6. Explanation of the third scene a-picture

Jacobi Relaxation Algorithm

Fig.2.7. Explanation of the variable declaration (by attaching units of measure) and "index expressions" (by displaying the neighborhoods of highlighted nodes)

 

Sparse matrix-vector multiplication

Example 3.1

Assume we have sparse matrix B and have to multiply it by vector V to obtain vector M. In addition, assume that B is prepared in the Yale format where three one-dimensional arrays (A, R, and C) are involved to define the matrix content. A contains nonzero elements of B (stored contiguously in the row-major order), and R and C possess integers for finding positions of the A elements in matrix B.

In this example, the explanation of different structure identifications, row folding/unfolding techniques, half-highlighting operations on nodes, restrictions for formula attachments and new annotations including cover frames and supportive drawings on Dynamics view frames is provided.

Main view of an °AIDA program is presented by the following figure below (Fig.3.1). In this program there is a declaration section and an algorithmic section. The declaration section consists of two top rows declaring five 1-D space structures and one 0-D structure (one-node structure) of the algorithmic activities. In addition, on each 1-D structure an integer variable is declared (A, R, C, V, M on structures st1, st2, st3, st4, and st5, respectively) and a size of the corresponding structure is pointed. The one-node structure of name st0 is defined for some activity, but no variables are associated with it.

The algorithmic section consists of six rows representing three CyberScenes for the input of initial data, the sparse matrix-vector multiplication, and the output of the result.

The input CyberScene is represented by an a-picture (and two rows). The scene a-picture has four traversal steps behind. Each step is an activity on space structures st1, st2, st3, and st4, respectively. Each activity has its own color and is defined by collective (triple-circle) operations presented to right of the a-picture. They are the inputs of initial values for variables A, R, C, and V. For example, the first operation defines the collective input of A for all nodes of the st1 structure from a txt-file. The input operation has two attributes to show a source of the getting data (in this case, it is a file micro-icon) and a specific name (ID) of the data item (in this case, it is A.txt).

The subsection of the sparse matrix-vector multiplication is also presented by one scene a-picture requiring the specification of three operations. Two operations (on half-highlighting nodes) are related to decision making operations about which nodes have to be involved at the next step of computation and which type of involvement is expected. The first half-highlighting operation assigns "a node for data reading" (for contour-highlighting activity) in the st2 structure if the number (column) of the node is greater than the value of C on the left contour-highlighting node in the st3 structure and if this number is also less or equal to the value of C on the right contour-highlighting node in the st2 structure. The second half-highlighting operation assigns "a node for data reading" in the st4 structure if the number (row) of the node is equal to the value of C on a contour-highlighting node of the st2 structure. The third operation to be specified for the scene a-picture is the dot product, the sum of multiplications of appropriate pairs, of A and V on the contour-highlighting nodes in structures st1 and st4. The micro-arrows under the SUM sign show that the nodes for the pairs from the structure st1 are selected in the left-to-right style and the nodes from the st4 structure are selected in the top-to-down style. The result of the dot product is assigned to variable M on full-highlighting nodes of structure st5. To see how the space structures are involved and where the operations have to be specified, Algorithmic Dynamics view of the scene can be displayed on demand as a set of tiled pictures of figure below (Fig. 3.4) or as a corresponding animation.

Sparse Matrix Vector Multiplication

Fig.3.1. Main view of sparse matrix-vector multiplication

The output subsection includes one scene represented by a corresponding a-picture. This a-picture requires one type of activity to be specified on nodes of space structure st5. This specification is done in the corresponding row after a micro-icon of collective operations to right of the a-picture. This is to output the result of computation (variable M) to a monitor by a collective operation on nodes of structure st5.

To obtain more compact version of this program (especially, when the user wants to focus on the sparse matrix-vector multiplication), the input/output subsections can be folded into one row. Fig.3.2 depicts such a version which is unfolded on demand.

Sparse Matrix Vector Multiplication

Fig.3.2. Main view of sparse matrix-vector multiplication with folded input/output subsections

The Algorithmic Dynamics view is a series of CyberFrames representing dynamical features of computation behind scene a-pictures of the Main view. For each a-picture of the input/output subsections, such features are presented by simple series of CyberFrames. So, the most important part of the Dynamics view is the dynamics related to the second scene a-picture representing the matrix-vector multiplication without the input/output.

The series of CyberFrames for this a-picture (Fig.3.3) is started with a cover CyberFrame representing the a-picture, space structures involved and parameters related to their sizes, as well as some text explanation of why they are involved. This CyberFrame, playing a role of annotation, is also supported by another annotation (also shown in Fig.3.3) to explain the Yale format of sparse matrices. In a larger format, the series is presented by Fig. 3.4.

Sparse Matrix Vector Multiplication

Fig.3.3. Algorithmic Dynamics view CyberFrames and an annotation for the cover CyberFrame

After the cover CyberFrame there are twelve steps of computation represented by twelve CyberFrames.

The CyberFrames show a skeleton of the algorithm by displaying three types of activity which should be defined on the space structures (appropriate flashings are applied if the tiles are observed as animation).

The first type is represented by the half-highlighting nodes of the st0 (one-node) structure; operations (attached to the node) define places and types of activity at the next frame. Some arrows at the next frame show these places and types and are interpreted as "assume that these are decisions of the half-highlighting operation from the previous frame." CyberFrames 1, 2, 4, 5, 7, 8, 10, and 11 are related to the first type of activity. In these CyberFrames there is a background cross behind the half-highlighting node. This cross points that the traversal scheme accepts places and types of activity only based on formulas presented by frame comments.

The second type is represented by the counter highlighting nodes pointing space positions where data are available "for reading." For example, in the first CyberFrame the half-highlighting is related to the decision operation based on data from two left nodes of structure st3. All CyberFrames have nodes related to data "for reading."

Sparse Matrix Vector Multiplication

Fig.3.4. Algorithmic Dynamics view CyberFrames

The third type is represented by the full highlighting nodes where data are available on "reading and writing." CyberFrames 3, 6, 9, and 12 are related to this type of activity performed on nodes of structure st5. For example, in CyberFrame 12 this type of activity is defined for the bottom node of structure st5 where corresponding operation can read data from contour-highlighting nodes of structure st1 and st4.

Sparse Matrix Vector Multiplication

Fig.3.5. An annotation for the first CyberFrame

An annotation to CyberFrame-1 (see Fig.3.5) clarifies that "the half-highlighting node operation selects, for the activity at CyberFrame-2, nodes of the light-green background structure where columns of nonzero elements in the first row of the sparse matrix are presented; these node positions (numbers presented at the nodes) are equal to or greater than 0 and less than 2; value 0 is taken from the blue contour-highlighting node and value 2 is taken from the orange contour-highlighting node (0 and 2 are presented in the nodes of the bottom horizontal structure of st3; they are illustrative indices in st2 to point two nodes where a column of the first nonzero element of the first row of the sparse matrix and a column of the first nonzero element of the second row are presented)."

Sparse Matrix Vector Multiplication

Fig.3.6. Annotations for the first three CyberFrames

An annotation to CyberFrame-2 (see Fig.3.6) clarifies that "two black arrows show a result of the half-highlighting node operation from CyberFrame-1: it is two contour-highlighting nodes in the structure with green background; in addition, another half-highlighting node operation selects, for the activity at CyberFrame-3, nodes of the light-yellow background structure which node positions (numbers presented at the nodes) are equal to 0 or 2, that are columns of nonzero elements of the first row in the sparse matrix; the column numbers are readable from the contour-highlighting nodes."

An annotation to CyberFrame-3 (see also Fig.3.6) clarifies that "two black arrows show a result of the half-highlighting node operation from CyberFrame-2: it is two contour-highlighting nodes in the structure with the light-yellow background; in addition, a full-highlighting node operation in structure st5 based on reading data from four contour-highlighting nodes is specified."

In general, CyberFrames 1-3 provide a basis for specifying an access to nonzero elements of the first row of the sparse matrix (to the elements included in the 1-D array of all nonzero elements) and for performing the dot-product operation of the first row elements and a vector involved.

CyberFrames 4-6, 7-9 and 10-12 are similar to CyberFrames 1-3; their focuses are on the dot-product operation of the second, third and fourth row elements and the vector involved, respectively.