Abstract reduction operation models in the LIME programming model

Reduction operations are frequently used operations which reduce the size of an input by selecting or combining its element and producing that as the output. Reduction operations can be easily handled in sequential computers in O(n) time. In fact in a parallel systems this time complexity can be reduced to O(log n) by using algorithms like tree-based reduction. However, this tempting decrease in the time complexity cannot be achieved without several platform specific tricks and optimizations. Therefore, in order to harness the power of parallel systems for reduction operations two major steps should be taken. First, a single standard model should be defined for such operations. Second, the model should be easily converted to different parallel platforms without any or with small changes to the underlying model. This thesis materializes the latter by defining a tool-chain called ‘LIME tool-chain’ and the former by defining dataflow models which can be fed into the tool-chain.Computer ScienceElectrical Engineering, Mathematics and Computer Scienc