Pith. sign in

REVIEW 2 major objections 5 minor 53 references

Simplification of Polyhedral Reductions in Practice

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims to provide the first complete push-button compiler implementation of reduction simplification, showing it rediscovering the fast-i-loops RNA algorithm, deriving ABFT checksums, and finding three new cubic RNA programs.

desk verdict A credible implementation of GR06 reduction simplification that rediscovers real algorithmic results, but the flagship push-button RNA claim hinges on an undocumented absolute-value encoding in the hand-written specification. read the letter →

arxiv 2411.17498 v1 pith:Y7GFSCUJ submitted 2024-11-26 cs.PL

Louis Narmour , Ryan Job , Tomofumi Yuki , Sanjay Rajopadhye This is my paper · ORCID
classification cs.PL
keywords polyhedralmodelreductionsimplificationprogramtransformationreusespacefacelatticecompileroptimizationasymptoticcomplexityRNAsecondarystructure
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that a compiler can automatically perform reduction simplification, a transformation that rewrites programs whose nested reductions recompute the same values into equivalent programs with strictly lower asymptotic complexity, without user guidance. The implementation selects a reuse direction at each recursion step by enumerating equivalence classes of candidate directions over the face lattice of the reduction body. On an RNA secondary-structure internal-loop recurrence that naively runs in O($N^{4}$), the compiler produces four distinct O($N^{3}$) programs, one matching a known 1999 algorithm and three previously unknown. The same machinery automatically derives checksum computations for fault-tolerant matrix multiplication, showing that algorithmic improvements historically requiring case-by-case human insight can become routine compiler transformations.

What carries the argument

The face lattice of the reduction body, together with the notion of thick faces for effectively saturated constraints, is the central data structure that carries the argument. At each facet, the sign of the inner product between a candidate reuse vector and the facet normal determines whether residual computation uses the reduction operator, its inverse, or neither; vectors inducing the same labeling form an equivalence class. The implementation enumerates these equivalence classes and selects the shortest integer reuse vector in each class, turning an infinite search over reuse directions into a finite set of candidate simplifications.

What would settle it

Feed the compiler an O($N^{4}$) RNA internal-loop recurrence written exactly as the published Zuker-style equation (with |p-i-j+q|) and inspect whether the generated four programs are all valid simplifications and whether the sign split on the loop-index expression appears in the compiler's output rather than in the user-supplied input; if the split is present in the input or any program is incorrect, the push-button claim for this headline case is falsified.

Watch

Extended reading notes

Core claim

The central claim is that the reuse latent in a polyhedral reduction can be systematically located and exploited by a push-button compiler pass. Simplification works by translating the reduction body along a vector in the reuse space (directions along which the reduction body reads the same input value) and discarding computation in the overlap, leaving residual computations only on facets. The paper's implementation makes this concrete by constructing the face lattice of the reduction body, labeling each facet according to whether the dot product of the reuse vector with the facet normal is positive, negative, or zero, and grouping reuse vectors into equivalence classes that induce the same labeling. Recursing over facets, each step reduces the polynomial degree of the complexity by one. On the O($N^{4}$) RNA internal-loop recurrence, the compiler rediscovers the cubic fast-i-loops algorithm and finds three further cubic programs; on matrix multiplication it derives the ABFT checksum equations automatically.

Load-bearing premise

The push-button claim for the RNA result rests on the input specification being a faithful, un-preprocessed encoding of the original O($N^{4}$) recurrence, including the absolute-value term, rather than a formulation that already bakes in the case split that the simplifier is supposed to discover.

Editorial extensions

If this is right

  • If the compiler works as claimed, asymptotic complexity improvements such as O(N^3) to O(N^2) become reproducible compiler transformations rather than manual algorithmic feats.
  • The RNA experiment shows that a single O(N^4) recurrence can yield multiple distinct O(N^3) algorithms, including previously unknown ones, suggesting that simplifying compilers can serve as tools for algorithmic discovery.
  • The automatic derivation of ABFT checksums for matrix multiplication indicates that fault-tolerance wrappers for other reduction-based computations could be generated systematically.
  • The successful implementation of recursive simplification, reduction decomposition, and distributivity means that each of these techniques is now a working compiler pass, verified by correct code generation on tested examples.
  • The paper's reported correctness checks and runtime measurements imply that the simplified RNA programs agree with the original for random inputs and exhibit the expected cubic asymptotic behavior.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The equivalence-class formulation provides a general template for algorithmic search over reuse directions that may extend to dependent reductions once scheduling is integrated with simplification.
  • If the tool can rediscover the fast-i-loops result with no human input, it is plausible that similar techniques could automate optimizations of other dynamic-programming recurrences, such as the Maximum Expected Accuracy equations mentioned in the paper.
  • The three novel RNA algorithms, while asymptotically equal, may have different constant factors or memory behavior; benchmarking them on real RNA sequences could reveal whether any are practically competitive.
  • A direct testable extension is to apply the simplifier to the dependent-reduction cases the paper flags as unsupported, checking whether the produced equations that 'do not admit a legal schedule' can be automatically repaired or rejected.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper describes an implementation of reduction simplification, the polyhedral transformation proposed by Gautam and Rajopadhye (GR06), built in the Alpha/AlphaZ system using isl. The authors claim the first complete push-button implementation of this transformation, including a heuristic for constructing equivalence classes and selecting reuse vectors. They evaluate it on several case studies: recursive simplification, reduction decomposition, distributivity, ABFT checksums for matrix multiplication, and an O(N^4) RNA internal-loop recurrence. For the RNA case, the paper reports that the compiler rediscovers Lyngsø et al.'s fast-i-loops algorithm and discovers three previously unknown O(N^3) variants. Correctness is checked against the original specification on random inputs, and asymptotic complexity is validated by runtime scaling and loop-iteration-count polynomials.

Significance. If the automation claims hold, this is a significant result: it converts a theoretical transformation into a usable compiler and shows that algorithmic improvements previously requiring manual insight can be reproduced automatically. The algebraic derivations in Section 5.4 and Section 6.1 are internally coherent, and the use of generated code plus empirical scaling checks is a sensible evaluation strategy. The main unresolved issue is whether the flagship RNA input is genuinely a single, un-decomposed recurrence or whether the user-supplied Alpha specification already encodes the sign split needed to handle the non-affine absolute value in Equation (27). This determines how much of the headline 'push-button from a single recurrence' claim is actually automated.

major comments (2)
  1. [§6.2, Eqs. (27)–(33)] The headline claim that four O(N^3) programs are discovered automatically from a single O(N^4) recurrence is not fully supported because the exact Alpha input is never shown. Equation (27) contains the non-affine term |p-i-j+q|, whereas the simplification machinery in Sections 3 and 4 (face lattice, dependence function, reuse space, facet labelings) is defined for affine/polyhedral expressions. Equations (32)–(33) exhibit a signed case split on l = p-i+q-j, but no transformation in Section 4 is described that would create such a split from an absolute value. If the supplied specification already encoded this split, or an equivalent piecewise case distinction, then the user supplied the decisive modeling decision. Please include the exact input specification, the full transformation log, and a precise statement of how absolute values are represented and whether the sign split is discovered by the compiler or assumed in the input.
  2. [§5, §6.2] The paper repeatedly refers to an 'accompanying artifact' but provides no URL, DOI, archive identifier, or reproducibility instructions. Since the contribution is an implementation and the empirical claims in Tables 2–3 and Figures 6–7 depend on generated code and compile times, the absence of a linked artifact blocks verification. Please provide a permanent artifact link and a minimal reproduction script that runs the compiler on each input specification and regenerates the four RNA programs.
minor comments (5)
  1. [Global] There are numerous typographical and grammatical errors, including 'intution' (Section 5), 'implemenation' and 'prgram' (Section 4.3), 'consraint' and 'saturing' (Section 3.1.1), 'equivalance' (Section 3.3), and 'bencharks' (Section 7). These should be cleaned up.
  2. [§6.4, Table 3, Figure 7] The compile-time measurements omit the compiler version, compiler flags, and machine specifications, and Figure 7 reports averaged ratios without indicating the number of runs or per-size variance. Please add this information.
  3. [§7, Eq. (34)] In the tensor-contraction example, the definition of Y_j sums over i, k, and j while the left-hand side is indexed only by j, and the bound 'i,k,j=1' is inconsistent with the later definition in Eq. (36). Please correct the indexing and the summation bounds.
  4. [Figure 6] The reference lines are labeled with constants 7e-9 and 1e-10; please state whether these constants are fitted to the data or chosen arbitrarily, since this affects how the reader interprets the visual complexity check.
  5. [Header] The ACM reference-format block in the header states '2018' and 'Conference'17' while the submission is dated 2024; this boilerplate should be updated to match the actual venue and year.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the simplification pipeline is implemented against GR06's prior theory, and the headline RNA and ABFT results are checked against external algorithms and the original specifications. The only caveat is that the Alpha input encoding of the non-affine absolute value in Eq. 27 is not printed, which is a verification gap rather than a demonstrated circular reduction.

full rationale

The paper's derivation chain is not circular. The underlying theory (GR06) is prior peer-reviewed work by a coauthor, but the paper's contribution is an implementation of that theory, not a re-derivation of it; the optimality and correctness claims rely on GR06's published, parameter-free theorems rather than on the target outputs, so this citation counts as independent support rather than load-bearing self-citation. The ABFT case (Section 5.4) algebraically transforms the row-sum specification into the checksum computation, and the resulting program is checked against the original specification. The RNA case (Section 6) produces four cubic programs from the recurrent specification, and those programs are validated for equality against the original O(N^4) program and benchmarked against Lyngsø et al.'s external 1999 algorithm. The loop-iteration polynomials in Table 2 are computed counts, not fitted parameters, and the measured runtimes are checked against those counts, so there is no fitted input being renamed as a prediction. The only substantive concern is that Section 6.2 says the authors 'developed a specification' for the RNA recurrence but does not print that Alpha input, leaving it unclear whether the non-affine |p-i-j+q| of Eq. 27 was encoded with the signed l >= 0 / l < 0 split that appears in Eqs. 32-33. If that split were supplied by the user, the 'single recurrence' push-button claim would be overstated. However, the paper provides no exhibited reduction showing that the input already contains the output structure, and per the hard rules, missing evidence of this kind is a verification/reproducibility limitation, not a demonstrated circular step. Self-citations to GR06 and AlphaZ are normal references to the paper's own theoretical and systems foundations and are not used to define away the target claim. Therefore the appropriate finding is no significant circularity, score 0.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The ledger contains no invented physical or mathematical entities; the only fitted numbers are plot-calibration constants. The heavy load is inherited theoretical assumptions (GR06 completeness) and faithfulness of the hand-written specifications.

free parameters (1)
  • Runtime-plot scale constants = 7e-9 (N^3 curve), 1e-10 (N^4 curve)
    Chosen so the reference complexity lines overlay the measured runtimes in Figure 6; they calibrate the plot, not the transformations, and do not affect any derived algorithm.
assumptions (3)
  • domain assumption The GR06 simplification framework is correct and optimal: at each recursion step any reuse vector from a given equivalence class yields the same polynomial-degree reduction, and recursing down the face lattice fully exploits all reuse.
    Invoked in Sections 3.3 and 3.4 as the theoretical basis; the paper does not re-prove it, and the implementation's completeness inherits it.
  • domain assumption Every test program has a faithful Alpha equational representation with affine indexing and a single size parameter; non-affine constructs such as the absolute value in the RNA recurrence are handled without injecting the target simplification.
    Stated in Section 4.3 and relied on for the fast-i-loops case (Section 6.2); the signed case split in Equations 32-33 shows where this assumption may be strained.
  • domain assumption Reduction operators are associative and commutative, and operators can be decomposed into single-variable reductions when a distributivity step applies.
    Used throughout Sections 5.2 to 5.4; for max and min operators the inverse is assumed absent, so simplification paths requiring inverses are pruned.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Simplification of Polyhedral Reductions in Practice." pith.science (2026). https://pith.science/paper/Y7GFSCUJ

@misc{pith2026241117498,
  author       = {Pith},
  title        = {Pith review of: Simplification of Polyhedral Reductions in Practice},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y7GFSCUJ}},
  note         = {Machine review of arXiv:2411.17498}
}
read the original abstract

Reductions combine collections of inputs with an associative (and here, also commutative) operator to produce collections of outputs. When the same value contributes to multiple outputs, there is an opportunity to reuse partial results, enabling reduction simplification. We provide the first complete push-button implementation of reduction simplification in a compiler. We evaluate its effectiveness on a range of real-world applications, and show that simplification rediscovers several key results in algorithmic improvement across multiple domains, previously only obtained through clever manual human analysis and effort. We also discover alternate, previously unknown algorithms, albeit without improving the asymptotic complexity.

Figures

Figures reproduced from arXiv: 2411.17498 by the authors.

Figure 1
Figure 1. ABFT checksums, (from Huang and Abraham [15]). The two quantities 𝛾𝑖 and 𝛾 ′ 𝑖 compute the same numeri￾cal value, and errors occurring during the computation of Equation 1 can be detected when their difference, |𝛾𝑖 − 𝛾 ′ 𝑖 |, is sufficiently large. More importantly, the 𝑂(𝑁 2 ) cost of computing Equations 2 and 3 is cheap relative to the main 𝑂(𝑁 3 ) computation in Equation 1. The complete derivation of Equation 3, … view at source ↗
Figure 2
Figure 2. Face lattice of D1 in Equation 7, the square with four edges (1-faces) and four vertices (0-faces) is shown on the left and D2 in Equation 8, the thick line segment with two vertices (0-faces) on the right. The equation has a reduction with the addition operator. The reduction body is defined over the domain D = { [𝑖, 𝑗] | 0 ≤ 𝑗 ≤ 𝑖 < 𝑁}, the red triangle in [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Simplification of a quadratic equation (compu￾tation defined over a triangle) to a linear complexity (the residual computation is defined only over the points in the bottom row). The 𝑖’th result, 𝑌𝑖 , is the accumulation of the values of the reduction body at points in the 𝑖’th diagonal of the triangle. The complexity of the equation is the number of integer points in D, namely 𝑂(𝑁 2 ). The reuse space is the null s… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Equivalence classes explored for the single-step simplification of Equation 12, with ⊕-faces highlighted in red, ⊖-faces in blue, and ⊘-faces not highlighted. 4.2 Selecting Candidate Reuse Vectors Given a particular labeling, L, the set of reuse vectors that induce the…
Figure 5
Figure 5. Figure 5: Alpha to C compilation pipeline. 5 Case Studies In this section, we evaluate the efficacy of our implementa￾tion based on the design choices described in Section 4. We confirm that we can find simplified versions of all examples and generate code that produces the corr…
Figure 6
Figure 6. Figure 6: Average runtimes of all generated fast-i-loops programs, plotted alongside (7e−9)𝑁 3 and (1e−10)𝑁 4 to verify the polynomial degree of the runtimes with respect to the problem size 𝑁. Lyngsø Hybrid 1 Hybrid 2 New Algorithm 0 0.5 1 1.5 1 1.08 1.25 1.33 1 1.02 1.35 1.37 …
Figure 7
Figure 7. Figure 7: Relative performance of the simplified fast-i-loops programs averaged across all problem sizes. implementation to find the simplifications in [PITH_FULL_IMAGE:figures/full_fig_p010_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

53 extracted references · 43 canonical work pages

  1. [1]

    S. M. Aji and R. J. McEliece. 2000. The Generalized Distributive Law. IEEE Transactions on Information Theory 46, 2 (March 2000), 325–343

    work page 2000

  2. [2]

    Katz, and Pierre-Yves Strub

    Xavier Allamigeon, Ricardo D. Katz, and Pierre-Yves Strub. 2022. For- malizing the Face Lattice of Polyhedra. Logical Methods in Computer Science Volume 18, Issue 2 (May 2022). https://doi.org/10.46298/lmcs- 18(2:10)2022 Publisher: Episciences.org

    doi:10.46298/lmcs- 2022

  3. [3]

    Amarasinghe and M

    S. Amarasinghe and M. Lam. 1993. Communication Optimization and Code Generation for Distributed Memory Machines. In The ACM SIGPLAN ‘93 Conference on Programming Language Design and Imple- mentation. ACM Press, Albuquerque, N.M., 126–138

    work page 1993

  4. [4]

    OpenMP Architecture Review Board. 2021. {OpenMP} Application Program Interface Version 5.2. 124–140. https://www.openmp.org/wp- content/uploads/OpenMP-API-Specification-5-2.pdf

    work page 2021

  5. [5]

    Sylvain Boulmé, Alexandre Maréchaly, David Monniaux, Michaël Périn, and Hang Yu. 2018. The Verified Polyhedron Library: an Overview. In 2018 20th International Symposium on Symbolic and Nu- meric Algorithms for Scientific Computing (SYNASC) . 9–17. https: //doi.org/10.1109/SYNASC.2018.00014

    arXiv 2018

  6. [6]

    Teresa Davies and Zizhong Chen. 2018. Correcting soft errors online in LU factorization. In Proceedings of the 22nd International Symposium on High-Performance Parallel and Distributed Computing (HPDC ’13) . Association for Computing Machinery, New York, NY, USA, 167–178. https://doi.org/10.1145/2462902.2462920 event-place: New York, New York, USA

    work page arXiv 2018

  7. [7]

    Yufei Ding and Xipeng Shen. 2017. GLORE: generalized loop redun- dancy elimination upon LER-notation. Proceedings of the ACM on Programming Languages 1, OOPSLA (Oct. 2017), 74:1–74:28. https: //doi.org/10.1145/3133898

    doi:10.1145/3133898 2017

  8. [8]

    Dirks and Niles A

    Robert M. Dirks and Niles A. Pierce. 2003. A partition function algorithm for nucleic acid secondary structure includ- ing pseudoknots. Journal of Computational Chemistry 24, 13 (2003), 1664–1677. https://doi.org/10.1002/jcc.10296 _eprint: https://onlinelibrary.wiley.com/doi/pdf/10.1002/jcc.10296

    work page doi:10.1002/jcc.10296 2003

Show all 53 references
  1. [9]

    Feautrier

    P. Feautrier. 1991. Dataflow analysis of array and scalar references. International Journal of Parallel Programming 20, 1 (Feb. 1991), 23–53

    1991

  2. [10]

    Paul Feautrier. 1992. Some efficient solutions to the affine scheduling problem. Part II. Multidimensional time. International Journal of Par- allel Programming 21, 6 (Dec. 1992), 389–420. https://doi.org/10.1007/ Conference’17, July 2017, Washington, DC, USA Narmour et al. BF01379404

    1992

  3. [11]

    Fornace, Nicholas J

    Mark E. Fornace, Nicholas J. Porubsky, and Niles A. Pierce. 2020. A Unified Dynamic Programming Framework for the Analysis of In- teracting Nucleic Acid Strands: Enhanced Models, Scalability, and Speed. ACS Synthetic Biology 9, 10 (Oct. 2020), 2665–2678. https: //doi.org/10.10...

    2020 doi

  4. [12]

    J. A. B. Fortes and D. I. Moldovan. 1984. Data broadcasting in linearly scheduled array processors. ACM SIGARCH Computer Architecture News 12, 3 (Jan. 1984), 224–231. https://doi.org/10.1145/773453.808186

    1984

  5. [13]

    Rajopadhye

    Gautam and S. Rajopadhye. 2006. Simplifying reductions. In Confer- ence record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL ’06) . Association for Computing Ma- chinery, New York, NY, USA, 30–41. https://doi.org/10.1145/1111037. 1111041

    2006 doi

  6. [14]

    Doug Hakkarinen, Panruo Wu, and Zizhong Chen. 2015. Fail-Stop Failure Algorithm-Based Fault Tolerance for Cholesky Decomposition. IEEE Transactions on Parallel and Distributed Systems 26, 5 (May 2015), 1323–1335. https://doi.org/10.1109/TPDS.2014.2320502 Conference Name: IEEE ...

    2015

  7. [15]

    Kuang-Hua Huang and Jacob A. Abraham. 1984. Algorithm-Based Fault Tolerance for Matrix Operations. IEEE Trans. Comput. C-33, 6 (June 1984), 518–528. https://doi.org/10.1109/TC.1984.1676475 Con- ference Name: IEEE Transactions on Computers

    1984

  8. [16]

    Irigoin and R

    F. Irigoin and R. Triolet. 1988. Supernode partitioning. In Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of program- ming languages (POPL ’88) . Association for Computing Machinery, New York, NY, USA, 319–329. https://doi.org/10.1145/73560.73588

    1988

  9. [17]

    Jacob, Jeremy D

    Arpith C. Jacob, Jeremy D. Buhler, and Roger D. Chamberlain. 2010. Rapid RNA Folding: Analysis and Acceleration of the Zuker Recur- rence. In 2010 18th IEEE Annual International Symposium on Field- Programmable Custom Computing Machines. IEEE, Charlotte, NC, USA, 87–94. https:...

    2010 doi

  10. [18]

    Sadayappan

    Martin Kong, Raneem Abu Yosef, Atanas Rountev, and P. Sadayappan

  11. [19]

    F. R. Kschischang, B. J. Frey, and H-A. Loeliger. 2001. Factor Graphs and the Sum-Product Algorithm. IEEE Transactions on Information Theory 47, 2 (Feb. 2001), 498–519

    2001

  12. [20]

    M. S. Lam. 1989. A Systolic Array Optimizing Computer . Kluwer Academic (Springer). https://doi.org/10.1007/978-1-4613-1705-0

    1989 doi

  13. [21]

    Le Verge, C

    H. Le Verge, C. Mauras, and P. Quinton. 1991. The ALPHA Language and its use for the Design of Systolic Arrays. Journal of VLSI Signal Processing 3, 3 (Sept. 1991), 173–182

    1991

  14. [22]

    Christian Lengauer. 1993. Loop parallelization in the polytope model. In CONCUR’93, Eike Best (Ed.). Springer, Berlin, Heidelberg, 398–416. https://doi.org/10.1007/3-540-57208-2_28

    1993 doi

  15. [23]

    Vincent Loechner and Doran K. Wilde. 1997. Parameterized Polyhedra and Their Vertices. IJPP: International Journal of Parallel Programming 25, 6 (Dec. 1997), 525–549. https://doi.org/10.1023/A:1025117523902 Publisher: Springer Verlag

    1997 doi

  16. [24]

    Bernhart, Christian Höner zu Siederdissen, Hakim Tafer, Christoph Flamm, Peter F

    Ronny Lorenz, Stephan H. Bernhart, Christian Höner zu Siederdissen, Hakim Tafer, Christoph Flamm, Peter F. Stadler, and Ivo L. Hofacker

  17. [25]

    Gloor, and David H

    Zhi John Lu, Jason W. Gloor, and David H. Mathews. 2009. Improved RNA secondary structure prediction by maximizing expected pair accuracy. RNA 15, 10 (Oct. 2009), 1805–1813. https://doi.org/10. 1261/rna.1643609 Company: Cold Spring Harbor Laboratory Press Distributor: Cold Spr...

    2009

  18. [26]

    R B Lyngsø, M Zuker, and C N Pedersen. 1999. Fast evaluation of internal loops in RNA secondary structure prediction. Bioinformatics 15, 6 (June 1999), 440–445. https://doi.org/10.1093/bioinformatics/15. 6.440

    1999 doi

  19. [27]

    David H. Mathews. 2004. Using an RNA secondary structure partition function to determine confidence in base pairs predicted by free energy minimization. RNA 10, 8 (Aug. 2004), 1178–1190. https://doi.org/10. 1261/rna.7650904 Company: Cold Spring Harbor Laboratory Press Distribu...

    2004

  20. [28]

    Christophe Mauras. 1989. Alpha : un langage equationnel pour la conception et la programmation d’architectures paralleles synchrones . These de doctorat. Rennes 1. https://theses.fr/1989REN10116

    1989

  21. [29]

    Marek Palkowski and Wlodzimierz Bielecki. 2017. Parallel tiled Nussi- nov RNA folding loop nest generated using both dependence graph transitive closure and loop skewing. BMC Bioinformatics 18, 1 (June 2017), 290. https://doi.org/10.1186/s12859-017-1707-8

    2017 doi

  22. [30]

    Marek Palkowski and Wlodzimierz Bielecki. 2020. Parallel tiled cache and energy efficient codes for O(n4) RNA folding algorithms.J. Parallel and Distrib. Comput. 137 (2020), 252–258. https://doi.org/10.1016/j. jpdc.2019.12.007

    2020 doi

  23. [31]

    J. Pearl. 1988. Probabilistic Reasoning in Intelligent Systems . Morgan Kaufmann, San Mateo, CA

    1988

  24. [32]

    Robert N. C. Pfeifer, Jutho Haegeman, and Frank Verstraete. 2014. Faster identification of optimal contraction sequences for tensor networks. Physical Review E 90, 3 (Sept. 2014), 033315. https: //doi.org/10.1103/PhysRevE.90.033315 Publisher: American Physical Society

    2014 doi

  25. [33]

    William Pugh. 1991. The Omega test: a fast and practical integer programming algorithm for dependence analysis. In Proceedings of the 1991 ACM/IEEE conference on Supercomputing (Supercomputing ’91). Association for Computing Machinery, New York, NY, USA, 4–13. https://doi.org/...

    1991

  26. [34]

    Quinton and V

    P. Quinton and V. Van Dongen. 1989. The Mapping of Linear Recur- rence Equations on Regular Arrays. Journal of VLSI Signal Processing 1, 2 (1989), 95–113. Publisher: Kluwer Academic Publishers, Boston

    1989

  27. [35]

    S. V. Rajopadhye. 1989. Synthesizing Systolic Arrays with Control Signals from Recurrence Equations. Distributed Computing 3 (May 1989), 88–105. Publisher: Elsevier Science, North Holland

    1989

  28. [36]

    Ramanujam and P

    J. Ramanujam and P. Sadayappan. 1990. Nested Loop Tiling for Dis- tributed Memory Machines. In Proceedings of the Fifth Distributed Memory Computing Conference, 1990. , Vol. 2. IEEE, Charleston, SC, USA, 1088–1096. https://doi.org/10.1109/DMCC.1990.556321

    1990

  29. [37]

    Xavier Redon and Paul Feautrier. 1994. Scheduling Reductions. In Proceedings of the 8th International Conference on Supercomputing (ICS ’94). ACM, New York, NY, USA, 117–125. https://doi.org/10.1145/ 181181.181319 event-place: Manchester, England

    1994

  30. [38]

    Redon and P

    X. Redon and P. Feautrier. 2000. Detection of Scans in the Polytope Model. Parallel Algorithms and Applications 15, 3-4 (2000), 229–263

    2000

  31. [39]

    Dongarra

    Robert Schreiber and Jack J. Dongarra. 1990. Automatic blocking of nested loops . Technical Report NASA-CR-188874. RIACS. https: //ntrs.nasa.gov/citations/19910023530 NTRS Author Affiliations: Re- search Inst. for Advanced Computer Science, Tennessee Univ. NTRS Document ID: 19...

    1990

  32. [40]

    G. R. Shafer and P. P. Shenoy. 1990. Probability Propagation. Annals of Mathematics and Artificial Intelligence 2, 1-4 (March 1990), 327–351

    1990

  33. [41]

    Sven Verdoolaege. 2010. isl: An Integer Set Library for the Polyhe- dral Model. In Mathematical Software – ICMS 2010 , Komei Fukuda, Joris van der Hoeven, Michael Joswig, and Nobuki Takayama (Eds.). Springer, Berlin, Heidelberg, 299–302. https://doi.org/10.1007/978-3- 642-1558...

    2010 doi

  34. [42]

    Wilde and S

    D. Wilde and S. Rajopadhye. 1995. The naive execution of affine recurrence equations. In Proceedings The International Conference on Application Specific Array Processors. IEEE, Strasbourg, France, 1–12. https://doi.org/10.1109/ASAP.1995.522900 ISSN: 1063-6862

    1995

  35. [43]

    Wolf and M

    M. Wolf and M. Lam. 1991. Loop transformation theory and an al- gorithm to maximize parallelism. IEEE Transactions on Parallel and Distributed Systems 2, 4 (Oct. 1991), 452–471

    1991

  36. [44]

    Wolf and Monica S

    Michael E. Wolf and Monica S. Lam. 1991. A data locality optimizing algorithm. In Proceedings of the ACM SIGPLAN 1991 conference on Pro- gramming language design and implementation - PLDI ’91 . ACM Press, Toronto, Ontario, Canada, 30–44. https://doi.org/10.1145/113445. 113449

    1991 doi

  37. [45]

    Michael Wolfe. 1987. Iteration Space Tiling for Memory Hierarchies. In Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing. Society for Industrial and Applied Mathematics, USA, 357–361

    1987

  38. [46]

    mostly-tileable

    David Wonnacott, Tian Jin, and Allison Lake. 2015. Automatic tiling of “mostly-tileable” loop nests. Amsterdam

    2015

  39. [47]

    Panruo Wu, Qiang Guan, Nathan DeBardeleben, Sean Blanchard, Ding- wen Tao, Xin Liang, Jieyang Chen, and Zizhong Chen. 2016. To- wards Practical Algorithm Based Fault Tolerance in Dense Linear Algebra. In Proceedings of the 25th ACM International Symposium on High-Performance P...

    2016

  40. [48]

    Cambridge Yang, Eric Atkinson, and Michael Carbin. 2021. Simplifying dependent reductions in the polyhedral model. Proceedings of the ACM on Programming Languages 5, POPL (Jan. 2021), 20:1–20:33. https: //doi.org/10.1145/3434301

    2021 doi

  41. [49]

    Tomofumi Yuki, Gautam Gupta, DaeGon Kim, Tanveer Pathan, and Sanjay Rajopadhye. 2013. AlphaZ: A System for Design Space Explo- ration in the Polyhedral Model. InLanguages and Compilers for Parallel Computing, Hironori Kasahara and Keiji Kimura (Eds.). Springer, Berlin, Heidelb...

    2013 doi

  42. [50]

    Kai Zhao, Sheng Di, Sihuan Li, Xin Liang, Yujia Zhai, Jieyang Chen, Kaiming Ouyang, Franck Cappello, and Zizhong Chen. 2021. FT-CNN: Algorithm-Based Fault Tolerance for Convolutional Neural Networks. IEEE Transactions on Parallel and Distributed Systems 32, 7 (July 2021), 1677...

    2021

  43. [51]

    M Zuker and P Stiegler. 1981. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Research 9, 1 (Jan. 1981), 133–148. https://www.ncbi.nlm.nih. gov/pmc/articles/PMC326673/

    1981

  44. [2011]

    Algorithms for Molecular Biology 6, 1 (Nov

    ViennaRNA Package 2.0. Algorithms for Molecular Biology 6, 1 (Nov. 2011), 26. https://doi.org/10.1186/1748-7188-6-26

    2011 doi

  45. [2023]

    In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’23)

    Automatic Generation of Distributed-Memory Mappings for Tensor Computations. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC ’23). Association for Computing Machinery, New York, NY, USA, 1–13. https://doi.org/...

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.