Grid Models

Contents

This class of models deals with the computations on the grids. The grid is partitioned into rectangular regions. The basic idea of this models is that we can distinguish between operations specific for one cell of the grid (or rectangular region) and operations specific for the whole row/column of the grid. So, the basic operations allowed (supported) by the archetype are the following independent operations:

• on rows only,
• on columns only,
• rectangular regions of the grid.

Right now, Grid Model doesn't allow the data exchange between cells of the grid directly. This allows to simplify computations on grid. However, later we will support exchange of the boundaries between rectangular regions of the grid directly, without intermediate operations on columns (rows).

For the purpose of efficiency we want to be able to gather the data together in row, column or grid form and operate on these blocks of data as a whole. So, in general, a program will be some combination of the three main blocks:

Figure 1. Two examples of program structure: Arbitrary combinations of row, column and region computations are allowed

In order to develop program, using the strategy of the Grid Model Archetype, arrange all computations you need to perform in 3 groups:

• computations on rows,
• computations on columns,
• and computations on grid.

So, in developing an algorithm, it is the programmer's responsibility to define the following:

1. Row computations: identify the procedure row_computations(some_rows), which will perform necessary computations on some subset of the grid's some_rows.
2. Column computations: identify the procedure column_computations(some_columns), which will perform necessary computations on some subset of the grid's some_columns.
3. Grid computations: identify the procedure grid_computations(some_regions), which will perform necessary computations on some_regions of the grid.
4. Boolean conditions: define boolean conditions, which will determine the structure of the program and/or program's termination conditions.

Click here to see an example of Grid Model.

The only archetype's requirement is that all operations should be separated into operations on rows, columns, or grid and appropriate procedures for performing these computations should be designed. The archetype doesn't restrict the programmer to one specific combination of these procedures. So, there is no unique procedure outline. Below you can find two correct main procedures of the archetype

procedure GridModel_1;
begin
   read_data_into_rows();
   while (boolean) do
      read_time_data_into_rows();
      put_data_into_row_form();
      row_computations();

      put_data_into_column_form();
      column_computations();

      put_data_into_grid_form();
      grid_computations();
      write_data();
   end while
end;

procedure GridModel_2;
begin
   read_data();
   while (boolean_1) do
      if (boolean_2) then begin
         read_time_data_into_rows();
         put_data_into_row_form();
         row_computations();

         put_data_into_column_form();
         column_computations();
      end
      else begin 
         read_time_data_into_columns();
         put_data_into_column_form();
         column_computations();

         put_data_into_row_form();
         row_computations();
      end;
      put_data_into_grid_form();
      grid_computations();

      write_data();
      end 
end;

Click here to see the small example of the Grid Model Archetype application in Fortran M.

The outline of the parallel program written using the Grid Model Archetype will not differ from the one given above. The only aspect that distinguishes the parallel implementation of the archetype from the sequential one is the implementation of procedures row_computations(), column_computations(), grid_computations(). Since direct data exchange between cells of the grid is not allowed, the computations on a cell of the grid are independent from the computations on other cells of the grid and thus can be executed in parallel. Similarly, row and column computations can also be executed in parallel. For example, if the sequential procedure row_computations() is as follows:

procedure row_computations(some_rows);
begin
   for (each row in some_rows) do begin
      { perform necessary computations on the current row}
   end for
ens;

Then the same procedure can be written in parallel by simply executing the for-loop in parallel:

procedure parallel_row_computations(some_rows);
begin
   parfor (each row in some_rows) do begin
      { perform necessary computations on the current row }
   end for
end;

Moreover, since the structures of parallel and sequential programs are so similar, it is very easy to write the sequential program first, debug it, and then edit it for parallel implementation.

The main issues that determine the performance of the programs written using Grid Archetype are:

• size of the regions on which computations are performed,
• location of the processes.

More details on performance evaluation for this archetype will be added at a later date.

An important application of this archetype is a model of air pollution. The CIT Air Quality Model is a model of air pollution in the Los Angeles area. The entire region is modelled as a three dimensional grid, where each vertical column is a cell. The input data of the model is the initial concentration of various pollutant and wind velocities at every step. The simulation is done for a specified number of hours. Every hour the levels of of various pollutants in each cell are written out to a file.

CLICK ON THIS PICTURE to see a movie that demonstrates the spread of pollutants over the Los Angeles basin using the CIT Air Quality Model.