Abstract: An algorithm is instance-optimal if it has the best possible asymptotic run time for every input instance. Such an algorithm is essentially perfect in terms of computational complexity. Instance-optimal algorithms are exceedingly rare, yet one of the most fundamental operations in data analytics - the relational join -…

Abstract: Multi-GPU systems have gained significant popularity in modern computing. While employing multiple GPUs intuitively offers aggregated memory capacity and combined computational parallelism, the delivered performance rarely keeps up with the increase in GPU counts. The scalability is severely limited by several factors,…