LeTSeE
the LEgal Transformation SpacE Explorator
Description
LeTSeE is a platform dedicated to computing and exploring the legal
affine scheduling space of a statically controlled program. It is
programmed as a library, offering services such as:
- a tunable algorithm for legal transformation space construction,
- various heuristics to traverse legal spaces,
- many auxiliary functions (graph manipulation, transformation generation, etc.)
The LeTSeE software is a part of a larger toolchain containing a set
of free software for program transformation and optimization in the
polyhedral model. It comprises also:
- FM, the Fourier-Motzkin Library, for manipulating Q-polyhedra
- PIPLib, a parametric integer programming solver
- PolyLib, a library for parametric integer polyhedra computation
- CLooG, a code generator in the polyhedral model
- Candl, a dependence analyzer
To enjoy full features of LeTSeE, it is strongly recommended to
install all the abovementionned software before installing LeTSeE. A package containing all of them is proposed in the download section.
Future plans: the next release of LeTSeE will contain
- Our most recent scalable traversal heuristic, relying on a Genetic
Algoritm leveraging dedicated GA operators tailored to preserve
legality.
- A third search space construction algorithm, emphasizing fusion
and permutability constraints.
- ...
Communication: three groups are available for subscription
- letsee-announce: receive announces about releases of the software.
- letsee-users: discuss any matter about how to use LeTSeE.
- letsee-dev: discuss any matter related to the software's implementation, bug fixes, desired features, etc...
Documentation
Please note that the two following documents are highly preliminary,
and incomplete. The documentation will be improved soon. In the
meantime, don't hesitate to contact the author for any question.
Download
- To download only the LeTSeE software: letsee-0.1.0.tar.gz
- To download the complete toolkit, including letsee-0.1.0.tar.gz, all the dependencies and an automated installer script (recommended): letsee-toolkit.tar.gz
Installation
The installation of LeTSeE follows the classical GNU library
scheme. Please specify the path of the 2 mandatory dependencies of
LeTSeE (FM and candl) to the configure script. The
configure script will automatically detect the location of
dependencies if --prefix=path/to/dir is specified and all
dependencies were installed in path/to/dir. Please note that the FM
library must have been compiled with the PIPLib support (it is
turned on by default in the LeTSeE Tooklit package)
$> tar xzf letsee-0.1.0.tar.gz
$> cd letsee-0.1.0
$> ./configure --prefix=/path/to/be/installed --with-fm=/path/to/fm/install --with-candl=/path/to/candl/install
$> make
The make check command can be used to make a test run of
LeTSeE. It will launch the space computation of the matmult
code fragment, generate the corresponding 912 transformations, compile
and run them on the target machine (provided it is a Linux embedding
GCC).
$> make check
There are several installation errors which may happen, beside a bug in
the software itself. Please check the following before contacting the
author:
- All dependencies are correctly installed, and were checked to work.
- All dynamic libraries are accessible for the LeTSeE binary. Typically,
you need to define the LD_LIBRARY_PATH variable with the paths to
all libraries on which LeTSeE depends on. You may also need to
specify in the PATH environment variable the path to access the CLooG and Candl binaries.
-
The base tester scripts of LeTSeE rely on the fact that you're using
unix-like computer, offering a few typical instructions (set_scheduler,
and assembly access to the Time Stamp Counter of the processor). If you
don't meet these requirements, you cannot use directly make
check. Don't worry, LeTSeE will work, you will just have to specify
some extra options, as detailed in the documentation.
Publications involving LeTSeE
In conferences
-
Louis-Noël Pouchet, Cédric
Bastoul, Albert Cohen and John Cavazos. Iterative optimization in the
polyhedral model: Part II, multidimensional time. In ACM SIGPLAN
Conference on Programming Language Design and Implementation
(PLDI'08), pp 90--100, ACM Press, Tucson, Arizona, June 2008.
[bibtex-entry] [pdf] [slides]
-
Louis-Noël Pouchet, Cédric
Bastoul, Albert Cohen and Nicolas Vasilache. Iterative optimization
in the polyhedral model: Part I, one-dimensional time. In IEEE/ACM Fifth International Symposium on Code Generation and Optimization (CGO'07), pp 144--156, IEEE Computer Society Press, San Jose, California, March 2007.
[bibtex-entry] [pdf] [slides]
In workshops
-
Louis-Noël Pouchet, Cédric
Bastoul, John Cavazos and Albert Cohen. A Note on the Performance Distribution of Affine Schedules. In 2nd Workshop on Statistical and Machine learning approaches to ARchitectures and compilaTion (SMART'08), Gotenborg, Sweden, January 2008.
[bibtex-entry] [pdf] [slides]
-
Louis-Noël Pouchet, Cédric
Bastoul and Albert Cohen. Iterative optimization in the polyhedral
model: the one-dimensional affine scheduling case. In 2nd HiPEAC
Industrial Workshop, Eindhoven, the Netherlands, October 2006.
[bibtex-entry] [pdf] [slides]
Miscellaneous
-
Louis-Noël Pouchet, Cédric
Bastoul and Albert Cohen. LeTSeE: the LEgal Transformation SpacE
Explorator. In Third International Summer School on Advanced
Computer Architecture and Compilation for Embedded Systems, pp
247--251, L'Aquila, Italia, July
2007. Extended abstract.
[bibtex-entry] [pdf] [poster]
-
Louis-Noël Pouchet. When
Iterative Optimization Meets the Polyhedral Model: One-dimensional
Date. Master thesis (University of Paris-Sud XI), Orsay,
France, October 2006.
[bibtex-entry] [pdf] [slides]
History
02/16/2008: Release of letsee-0.1.0
- Initial release of the project.