AsAP Mapping Project

Algorithms and Software Tools for Mapping Arbitrarily Connected Tasks
onto an Asynchronous Array of Simple Processors

Description

The AsAP Mapping Project is the design and implementation of algorithms and software tools for assigning interconnected tasks to processor locations in a 2D-mesh array. The mapping algorithms are designed to maximize nearest neighbor communication and minimize array area, but still have the ability to utilize non-nearest neighbor routing networks. Various placement and routing techniques, based primarily on simulated annealing and maze routing, are used to obtain high quality results in a relatively short period of time for a number of applications.

Motivation for an automated mapping algorithm is the ability to quickly and efficiently map complex applications to a 2D-mesh parallel architecture, such as AsAP. Without such an algorithm, programming these highly parallel architectures can be challenging when applications are distributed across possibly hundreds of processing elements that must communicate efficiently. An automated tool, such as the one developed here, is necessary to deal with this seemingly infinite number of processing elements. Also with transistor sizes shrinking, fabrication errors and leakage are becoming big problems which can be mitigated through mapping optimizations.

Feature Overview

Screenshots


Example showing an FFT application being designed.


One possible mapping for the FFT shown previously.

Install Notes

To install the AsAP Mapping Tool on Windows you will first need to install the GTK+ Runtime Environment. You can find this installer cached locally below (or from gimp-win.sourceforge.net). After installing GTK+, download the Windows Binaries from below and extract its contents to any location (Ex. C:\AsapMap). You should create a shortcut on your desktop pointing to asapmap.bat inside the extracted folder (using the included icon if you wish). The asapmap.bat file will setup your path correctly to find the needed libraries and launch the mapping tool. Any output from the mapping tool will be displayed in the console window that was also opened when the application was started. A number of folders are created when the binaries are extracted, including folders for storing projects and modules.

To compile the source code simply download the file from below and extract it using tar, tar -jxvf mapping-*.tar.bz2. Also download and compile the boost C++ libraries from the resources below. Documentation for compiling boost can be found on the boost website. The primary platform for compilation is Linux but with the proper setup it can be compiled and run on MacOS X, and Windows (rather involved). Refer to the Readme files for both asapmap and libamap contained in the source archive for more information about compiling the mapping tool and the structure of the program and the directories.

For additional help email: ewwork(AT)ucdavis(DOT)edu

Downloads

Source Code - Version: 1.0.1 (273K)
Windows Binaries - Version: 1.0.0 (6.3M)
GTK+ Runtime Environment (5.8M)

Documentation

Master's Thesis
AsAP Project Website
Programming AsAP

Resources

Boost C++ Libraries
GNOME Platform Libraries