maindoc.tex

TGFF省城程序

\documentclass[english]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{geometry}
\usepackage{graphics}
\geometry{verbose,letterpaper,tmargin=1in,bmargin=1in,lmargin=1in,rmargin=1in}
\usepackage{babel}
\usepackage{pslatex, xspace}

\newcommand{\cpp}{\mbox{C\raisebox{0.25ex}[0cm][0cm]{++}}\xspace}

\begin{document}

\title{Task Graphs for Free (TGFF v3.0)}


\author{Keith Vallerio}

\maketitle
\tableofcontents{}
\renewcommand{\bottomfraction}{0.9} 
\renewcommand{\topfraction}{0.8}

\section{Introduction}

TGFF was originally developed in 1998 by R.P.\ Dick and D.L.\ Rhodes
to facilitate standardized random benchmarks for scheduling and allocation
research, in general, and hardware-software co-synthesis research, in
particular.  TGFF is suitable for many applications that require generating
pseudo-random graphs.  K. Vallerio subsequently updated and enhanced the code
and documentation. The latest version (3.0) expands on TGFF features,
providing a highly configurable random graph generator capable of generating
several types of random graphs. This document includes installation
instructions as well as a list of features.

\section{Installation}

Installation of TGFF should be rather straightforward. 

\begin{enumerate}
\item Download package
\item \textbf{\emph{mkdir}} (target dir)
\item \textbf{\emph{cd}} (target dir)
\item \textbf{\emph{tar -xzvf}} (filename)
\item Read \textbf{README} 
\item \textbf{\emph{make}}
\item Enjoy.
\end{enumerate}

\subsection{Requirements}

The only requirement should be a \cpp compiler. There may be complications
since the code has been extended to be more compliant with the ANSI \cpp
standard. Windows users may also have difficulty in porting the
makefile. Installing the graph viewing program VCG adds to the usefulness of
TGFF as well.  Note that VCG output is not available for the packed schedules
because the packed schedules routines are independent from the main source
code.

\subsubsection{\label{sec:vcg}Supplemental requirements (VCG)}

TGFF can generate visual graphs in both EPS and VCG formats. The EPS
files should be readable by any postscript viewing program. The VCG
format files require the graph visualization program VCG to view the
files, but provides color and better zoom ability. VCG is a very useful
graph visualization program which can be found at:

\begin{itemize}
\item http://rw4.cs.uni-sb.de/users/sander/html/gsvcg1.html.
\end{itemize}
TGFF is still useful without this program, but I highly recommend
using it. If you are unfamiliar with VCG, the basic keys you need
to know are:

\begin{itemize}
\item `=': Zoom in 
\item `-': Zoom out
\item `q': Quit
\item Arrows: Move the graph left, right, up and down
\end{itemize}

\section{Algorithms}

TGFF 3.0 is able to generate a variety of graph types based on the
commands found in the source (*.tgffopt) file.  In addition to
supporting the orginal TGFF algorithm\footnote {The traditional
algorithm can be found in ``TGFF: Task Graphs for Free'' by
R.P. Dick, D.L. Rhodes, and W.  Wolf, in \textbf{Proc.
Int. Workshop Hardware/Software Codesign}, pp. 97-101, Mar. 1998.},
a new, highly configurable graph generation method has been added.
The new algorithm generates random graphs in a much different manner
than the original algorithm.  Although the new algorithm is highly
configurable, the old algorithm was retained since there are some
graph types, such as trees, that are much easier to generate using
the old algorithm.  The algorithms differ in the method they use to
connect nodes in the graph, but they share several common features.

\subsection{General features}
TGFF allows users to determine the type and number of graphs that
will be generated based on the set of parameters in the source file.
This allows users to easily create several different graphs with
similar characteristics.  Some parameters, such as the number of
start (source) nodes, may be specified directly by the user.  Other
parameters may not be specified directly.  (The number of nodes in
the graph is a lower bound.)  Depending on the connectivity of the
graph, TGFF will generate one or multiple sink nodes.  However,
currently, TGFF is limited to generating directed acyclic graphs
(DAGs).

Task graph labels (default is TASK\_GRAPH) and starting index number
can be set via parameters as well.  This allows users to generate
multiple sets of task graphs with unique IDs.  A set of task graphs
can be generated using one set of parameters and writen using
\emph{tg\_write}, then change the parameters and generate a another
set of task graphs.

\subsubsection{Periods and deadlines}
Each graph is assigned a period and a deadline based on the length
of the maximum path in the graph and the \emph{task\_trans\_time}
parameter.  The \emph{task\_trans\_time} is the average time per
node and edge traversal.  The parameter list, \emph{period\_mul}, is
used to scale the graphs relative to each other.  Each time a graph
is generated a number in the \emph{period\_mul} list is selected
randomly.  This value is used to stretch or shrink the graphs
relative to each other.  Thus, graphs generated using the values 0.5
and 2 for \emph{period\_mul} would result in some graphs containing
approximately 4x as many nodes as others.  A hyperperiod is
generated based on the LCM of the periods of the task
graphs.\footnote {Those interested in reading more about this topic
are referred to ``Scheduling periodically occurring tasks on
multiple processors'' by E. L. Lawler and C. U. Martel, in
\textbf{Information Processing Letters}, vol. 7, pp. 9-12,
Feb. 1981.}

\subsubsection{Tables}
Each node and edge generated by TGFF is given a type.  Those types
may be used directly.  However, some users have found it valuable to
use the node/edge type to index into a table.  As a result, there
are two types of tables that TGFF will generate.  The first is the
transmission (edges) table and the second is the pe (node) table.
The difference between these two tables is that the transmission
table, generated by \emph{trans\_write}, will create one entry per
edge type and the pe table, generated by \emph{pe\_write}, will
create one entry per node type.

The name and starting index number can be set via parameters.  The
three most common commands used with tables are: \emph{table\_cnt},
\emph{table\_attrib}, and \emph{type\_attrib}.  \emph{table\_cnt}
sets the number of tables to be generated.  \emph{table\_attrib}
sets parameters to be listed for the whole table.
\emph{type\_attrib} sets parameters for each entry in the table.

 For example, Table~\ref{sampletable} presents a table generated for
by \emph{pe\_write}.  Since \emph{table\_cnt} was set to two, there
are two tables that were generated.  The first line contains the
table label and the index of the first table.  The next line is a
comment, because it starts with a ``\#'' character.  The line
following it has 3 values.  These values were set by the
\emph{table\_attrib} command.  The following line contains another
comment.  The next four lines are set by the \emph{type\_attrib}.
Note, the first item in each line is the type number.  Thus, these
tables had two parameters listed for \emph{table\_attrib} and two
listed for \emph{type\_attrib}.

\begin{table*}\centering
%\renewcommand{\arraystretch}{1.3}
\caption{Processor table example}
\label{sampletable}
\begin{tabular}{|l l l|} \hline
\@PROCESSOR 0 \{ && \\ 
~~~\# price (USD) & power (W) & area (sq. mm) \\
~~~~~~14 & 0.533 & 7.5 \\ 
~~~\# type & run time (ms) & memory (KB) \\ 
~~~~~~0 & 291428 & 348 \\ 
~~~~~~1 & 36265 & 256 \\ 
~~~~~~2 & 19323 & 312 \\ 
~~~~~~3 & 43251 & 724 \\ 
\} && \\ 
&& \\
\@PROCESSOR 1 \{ && \\ 
~~~\# price (USD) & power (W) & area (sq. mm) \\
~~~~~~11 & 0.648 & 6.9 \\ 
~~~\# type & run time (ms) & memory (KB) \\ 
~~~~~~0 & 260032 & 380 \\ 
~~~~~~1 & 36463 & 212 \\ 
~~~~~~2 & 38269 & 340 \\ 
~~~~~~3 & 26035 & 792 \\ 
\} && \\ \hline
\end{tabular}
\end{table*}

\subsection{Original algorithm}
The original algorithm iteratively adds nodes to construct a graph using
limits on the maximum in and out degrees of each node. The file,
\textbf{\emph{origin1.eps}}, contains a task graph generated using
the old algorithm with ``in'' and ``out'' degree maximum value equal
to two. By setting the ``in'' degree to one and the ``out'' degree
to a higher value, a tree can be generated such as the one in
\textbf{\emph{tree1.eps}}.  These two files,
\textbf{\emph{origin1.eps}} and \textbf{\emph{tree1.eps}}, are
displayed in Figures \ref{oldalg}(a) and (b), respectively.

\begin{figure}
{\centering \resizebox*{5in}{3.5in}{{\includegraphics{origin1}}
{\includegraphics{tree1}}} \par}
\caption{\label{image:oldalg} Using the old algorithm to generate
  graphs.  (a) In/Out degree 2 2 (b) In/Out degree 1 2}
\label{oldalg}\end{figure}

\subsection{New algorithm}

The new method is capable of generating several types of random graphs
including series-parallel chains. \textbf{\emph{sp\_rand1.eps}} is
an example of a random graph that is generated using the new method.
The file, \textbf{\emph{sp\_simple.eps}}, shows a simple example of
a series-parallel task graph.

The series-parallel algorithm generates a root node that is
connected to a set of chains of nodes.  A chain of nodes is one or
more nodes that are linked together in series to form a chain.  The
algorithm gets its name, series-parallel, since the root node is
attached to an arbitrary number of these chains of nodes.  The
number of chains and length of each chain are set by the TGFF
commands \emph{series\_wid} and \emph{series\_len}.  Another
parameter, \emph{series\_must\_rejoin}, will generate an extra (sink)
node that will connect to the end of each chain.  If that parameter
is set to zero, \emph{series\_subgraph\_fork\_out} allows the user to
define the probability that these chains will not rejoin at the end.
A root node connected to a set of chains of nodes along with the
corresponding sink node (if it is generated) is called an
series-parallel unit (SPU).

The algorithm defined above is good for creating a few chains of
nodes, but generates simple graphs.  To make the algorithm more
applicable, it is performed recursively.  The series-parallel
algorithm first generates one SPU.  If the graph has less than the
required number of nodes, one node inside the SPU is designated the
root of a new SPU.  This process is repeated until the graph has the
requested number of nodes.

To increase the generality of the task graphs generated using this
method, parameters were added to generate arcs between chains of
nodes within a SPU and across SPUs.  These commands are
\emph{series\_local\_xover} and \emph{series\_global\_xover}.  Used
alone, these commands allow the user to generate a random graph that
does not have series-parallel structure.  By setting the length and
width of each SPU to 0 and using \emph{series\_global\_xover}, a
random graph will be generated with only the number of edges
specified by \emph{series\_global\_xover}.  An example based on this
method, \textbf{\emph{sp\_rand.tgff}}, can be found in the examples
file.  (Note that this is different from the
\textbf{\emph{sp\_rand1.tgffopt}} found in this directory).

By combining the random graph generation method with the
series-parallel method, a wide variety of graphs can be generated.
The two files created using the new algorithm,
\textbf{\emph{sp\_rand1.eps}} and \textbf{\emph{sp\_simple.eps}},
are displayed in Figures \ref{newalg}(a) and (b), respectively.

\begin{figure}
{\centering \resizebox*{5in}{3.5in}{{\includegraphics{sp_rand1}}
{\includegraphics{sp_simple}}} \par}
\caption{\label{image:newalg} Using the new algorithm to generate
  graphs.  (a) Random graph  (b) Series-parallel graph}
\label{newalg}\end{figure}

\textbf{Note:} The original algorithm is currently the default.
 To use the new algorithm, use the command \emph{gen\_series\_parallel}.


\section{How TGFF works}

In general, TGFF accepts input parameters from a \textbf{\emph{tgffopt}}
file. A list of features TGFF currently supports are listed below.
It is recommended that new users examine the examples in Section
\ref{examples} to get a basic understanding of how TGFF commands work.

\subsection{Usage}

To invoke TGFF, use the following comand:

\begin{itemize}
\item tgff {[}filename{]}
\end{itemize}

\subsubsection{Key}

\begin{enumerate}
\item A `\textbackslash{}' can be used to enter multi-line commands.
\item A `\#' at the start of a line comments out the line.
\item Average and Multipliers: These multiplier indicate a value that is
used to scale a random number {[}-1, 1) and added to the average to
obtain pseudo-random values. For example, an average of 4 with a multiplier
of 2 ranges from {[}2, 6).
\item Tasks and nodes are used interchangeably
\item Transmits and arcs are used interchageably
\end{enumerate}

\subsubsection{Datatypes}

The following is a list of data types used for TGFF's parameters:

\begin{itemize}
\item <string>: a string of characters
\item <int>: an integer number