Code and Circuit Generation for Efficient Projection Computations on Embedded Platforms
Open access
Author
Date
2014-04Type
- Master Thesis
ETH Bibliography
yes
Altmetrics
Abstract
Minimum Euclidian norm projection onto polyhedral sets is a core operation in first-order methods for convex optimization problems with convex affine inequality constraints. This projection is performed at every iteration of the solver, which makes its efficiency critical for the overall performance. For many practical problems in embedded optimization, this projection can be explicitly written as an evaluation of a piecewise affine function. State-of-the-art architectures evaluate such functions by iteratively traversing binary trees. This thesis describes a novel approach that uses graph representations of the computations to be performed to optimize operation sharing. Automatic circuit generation is used to obtain problem-specific implementations that can significantly outperform current reference implementations with only modest increases in circuit size. The results are implemented in a software toolchain and quantitative comparisons with existing toolchains are made, demonstrating the effectiveness of the approach. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000536577Publication status
publishedPublisher
ETH ZurichOrganisational unit
08814 - Smith, Roy (Tit.-Prof.)
More
Show all metadata
ETH Bibliography
yes
Altmetrics