id: 05940004
dt: a
an: 05940004
au: Ranjan, Desh; Savage, John; Zubair, Mohammad
ti: Strong I/O lower bounds for binomial and FFT computation graphs.
so: Fu, Bin (ed.) et al., Computing and combinatorics. 17th annual
    international conference, COCOON 2011, Dallas, TX, USA, August 14‒16,
    2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22684-7/pbk).
    Lecture Notes in Computer Science 6842, 134-145 (2011).
py: 2011
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-22685-4_12
ab: Summary: Processors on most of the modern computing devices have several
    levels of memory hierarchy. To obtain good performance on these
    processors it is necessary to design algorithms that minimize I/O
    traffic to slower memories in the hierarchy. In this paper, we propose
    a new technique, the boundary flow technique, for deriving lower bounds
    on the memory traffic complexity of problems in a two-level memory
    hierarchy architectures. The boundary flow technique relies on
    identifying sub-computation structure corresponding to equal
    computations with a minimum number of boundary vertices, which in turn
    is related to the vertex isoperimetric parameter of a computation
    graph. We demonstrate that this technique results in stronger lower
    bounds for memory traffic on memory hierarchy architectures for
    well-known computation structures: the binomial computation graphs and
    FFT computation graphs.
rv: