O'Reilly logo

Advanced Backend Optimization by Sid Touati, Benoit de Dinechin

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Appendix 4

Efficiency of Non-Positive Circuit Elimination in the SIRA Framework

A4.1. Experimental setup

These experiments were conducted by Sébastien Briais on the stand-alone data dependence graph (DDG) described in Appendix 1. We assume Τ = {GR, BR, FP}. We used a regular Linux workstation (Intel Xeon, 2.33 GHz, 9 GB of memory).

A4.1.1. Heuristics nomenclature

Our methods to avoid the creation of non-positive circuits are of three types:

1) UAL is the (pessimistic) naive heuristic that consists of applying SIRALINA with unit-assumed-latencies (UAL) semantics only. That is, we do not consider non-unit-assumed-latencies (NUAL) code semantics from the beginning.
2) CHECK is the reactive strategy that consists of first applying SIRALINA with NUAL semantics. If a non-positive circuit is detected, we apply a second pass, which applies SIRALINA but with a UAL semantics.
3) SPE is the proactive strategy, based on shortest paths equations (SPE). If n(n ≥ 1) is the bound on the maximal number of iterations used, we write SPEn.

A4.1.2. Empirical efficiency measures

For each heuristic of non-positive circuit elimination, for each DDG and for each initiation interval II between MII and L (L is a fixed upper bound on the admissible values for II), we measured the execution time taken by each heuristic (listed above) to minimize the register requirement; we also recorded the number of registers computed by the three methods (UAL, CHECK and SPE). We are going to examine these results in the ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required