vpr/SRC/base/SetupGrid.c

Go to the documentation of this file.

/**
 * @file
 * Author: Jason Luu
 * Date: October 8, 2008
 *
 * Initializes and allocates the physical logic block grid for VPR.
 */

#include <string.h>
#include <stdio.h>
#include <assert.h>
#include "util.h"
#include "vpr_types.h"
#include "globals.h"
#include "SetupGrid.h"
#include "read_xml_arch_file.h"

static void CheckGrid(void);
static t_type_ptr find_type_col(INP int x);


/** Create and fill FPGA architecture grid.         */
void
alloc_and_load_grid(INOUTP int *num_instances_type)
{

    int i, j;
    t_type_ptr type;

#ifdef SHOW_ARCH
    FILE *dump;
#endif


    /* To remove this limitation, change ylow etc. in t_rr_node to        *
     * * be ints instead.  Used shorts to save memory.                      */
    if((nx > 32766) || (ny > 32766))
        {
            printf("Error:  nx and ny must be less than 32767, since the \n");
            printf("router uses shorts (16-bit) to store coordinates.\n");
            printf("nx: %d.  ny: %d.\n", nx, ny);
            exit(1);
        }

    assert(nx >= 1 && ny >= 1);

    grid = (struct s_grid_tile **)alloc_matrix(0, (nx + 1),
                                               0, (ny + 1),
                                               sizeof(struct s_grid_tile));

    /* Clear the full grid to have no type (NULL), no capacity, etc */
    for(i = 0; i <= (nx + 1); ++i)
        {
            for(j = 0; j <= (ny + 1); ++j)
                {
                    memset(&grid[i][j], 0, (sizeof(struct s_grid_tile)));
                }
        }

    for(i = 0; i < num_types; i++)
        {
            num_instances_type[i] = 0;
        }

    /* Nothing goes in the corners. */
    grid[0][0].type = grid[nx + 1][0].type = EMPTY_TYPE;
    grid[0][ny + 1].type = grid[nx + 1][ny + 1].type = EMPTY_TYPE;
        num_instances_type[EMPTY_TYPE->index] = 4;

    for(i = 1; i <= nx; i++)
        {
            grid[i][0].blocks =
                (int *)my_malloc(sizeof(int) * IO_TYPE->capacity);
            grid[i][0].type = IO_TYPE;

            grid[i][ny + 1].blocks =
                (int *)my_malloc(sizeof(int) * IO_TYPE->capacity);
            grid[i][ny + 1].type = IO_TYPE;

            for(j = 0; j < IO_TYPE->capacity; j++)
                {
                    grid[i][0].blocks[j] = EMPTY;
                    grid[i][ny + 1].blocks[j] = EMPTY;
                }
        }

    for(i = 1; i <= ny; i++)
        {
            grid[0][i].blocks =
                (int *)my_malloc(sizeof(int) * IO_TYPE->capacity);
            grid[0][i].type = IO_TYPE;

            grid[nx + 1][i].blocks =
                (int *)my_malloc(sizeof(int) * IO_TYPE->capacity);
            grid[nx + 1][i].type = IO_TYPE;
            for(j = 0; j < IO_TYPE->capacity; j++)
                {
                    grid[0][i].blocks[j] = EMPTY;
                    grid[nx + 1][i].blocks[j] = EMPTY;
                }
        }

    num_instances_type[IO_TYPE->index] = 2 * IO_TYPE->capacity * (nx + ny);

    for(i = 1; i <= nx; i++)
        {                       /* Interior (LUT) cells */
            type = find_type_col(i);
            for(j = 1; j <= ny; j++)
                {
                    grid[i][j].type = type;
                    grid[i][j].offset = (j - 1) % type->height;
                    if(j + grid[i][j].type->height - 1 - grid[i][j].offset >
                       ny)
                        {
                            grid[i][j].type = EMPTY_TYPE;
                            grid[i][j].offset = 0;
                        }

                    if(type->capacity > 1)
                        {
                            printf(ERRTAG
                                   "In FillArch() expected core blocks to have capacity <= 1 but "
                                   "(%d, %d) has type '%s' and capacity %d\n",
                                   i, j, grid[i][j].type->name,
                                   grid[i][j].type->capacity);
                            exit(1);
                        }

                    grid[i][j].blocks = (int *)my_malloc(sizeof(int));
                    grid[i][j].blocks[0] = EMPTY;
                    if(grid[i][j].offset == 0)
                        {
                            num_instances_type[grid[i][j].type->index]++;
                        }
                }
        }

    CheckGrid();

#ifdef SHOW_ARCH
    /* DEBUG code */
    dump = my_fopen("grid_type_dump.txt", "w", 0);
    for(j = (ny + 1); j >= 0; --j)
        {
            for(i = 0; i <= (nx + 1); ++i)
                {
                    fprintf(dump, "%c", grid[i][j].type->name[1]);
                }
            fprintf(dump, "\n");
        }
    fclose(dump);
#endif
}

void
freeGrid()
{
    int i, j;

    for(i = 0; i <= (nx + 1); ++i)
        {
            for(j = 0; j <= (ny + 1); ++j)
                {
                    free(grid[i][j].blocks);
                }
        }
    free_matrix(grid, 0, nx + 1, 0, sizeof(struct s_grid_tile));
}


static void
CheckGrid()
{
    int i, j;

    /* Check grid is valid */
    for(i = 0; i <= (nx + 1); ++i)
        {
            for(j = 0; j <= (ny + 1); ++j)
                {
                    if(NULL == grid[i][j].type)
                        {
                            printf(ERRTAG "grid[%d][%d] has no type.\n", i,
                                   j);
                            exit(1);
                        }

                    if(grid[i][j].usage != 0)
                        {
                            printf(ERRTAG
                                   "grid[%d][%d] has non-zero usage (%d) "
                                   "before netlist load.\n", i, j,
                                   grid[i][j].usage);
                            exit(1);
                        }

                    if((grid[i][j].offset < 0) ||
                       (grid[i][j].offset >= grid[i][j].type->height))
                        {
                            printf(ERRTAG
                                   "grid[%d][%d] has invalid offset (%d)\n",
                                   i, j, grid[i][j].offset);
                            exit(1);
                        }

                    if((NULL == grid[i][j].blocks) &&
                       (grid[i][j].type->capacity > 0))
                        {
                            printf(ERRTAG
                                   "grid[%d][%d] has no block list allocated.\n",
                                   i, j);
                            exit(1);
                        }
                }
        }
}

static t_type_ptr
find_type_col(INP int x)
{
    int i, j;
    int start, repeat;
    float rel;
    boolean match;
    int priority, num_loc;
    t_type_ptr column_type;

    priority = FILL_TYPE->grid_loc_def[0].priority;
    column_type = FILL_TYPE;

    for(i = 0; i < num_types; i++)
        {
            if(&type_descriptors[i] == IO_TYPE ||
               &type_descriptors[i] == EMPTY_TYPE ||
               &type_descriptors[i] == FILL_TYPE)
                continue;
            num_loc = type_descriptors[i].num_grid_loc_def;
            for(j = 0; j < num_loc; j++)
                {
                    if(priority <
                       type_descriptors[i].grid_loc_def[j].priority)
                        {
                            match = FALSE;
                            if(type_descriptors[i].grid_loc_def[j].
                               grid_loc_type == COL_REPEAT)
                                {
                                    start =
                                        type_descriptors[i].grid_loc_def[j].
                                        start_col;
                                    repeat =
                                        type_descriptors[i].grid_loc_def[j].
                                        repeat;
                                    if(start < 0)
                                        {
                                            start += (nx + 1);
                                        }
                                    if(x == start)
                                        {
                                            match = TRUE;
                                        }
                                    else if(repeat > 0 && x > start
                                            && start > 0)
                                        {
                                            if((x - start) % repeat == 0)
                                                {
                                                    match = TRUE;
                                                }
                                        }
                                }
                            else if(type_descriptors[i].grid_loc_def[j].
                                    grid_loc_type == COL_REL)
                                {
                                    rel =
                                        type_descriptors[i].grid_loc_def[j].
                                        col_rel;
                                    if(nint(rel * nx) == x)
                                        {
                                            match = TRUE;
                                        }
                                }
                            if(match)
                                {
                                    priority =
                                        type_descriptors[i].grid_loc_def[j].
                                        priority;
                                    column_type = &type_descriptors[i];
                                }
                        }
                }
        }
    return column_type;
}