Combating Randomness: Towards Efficient Data-Intensive Applications Using Software-Hardware Co-Design

Abstract

The emergence of data-intensive applications has a tremendous impact on our daily life. For example, social media processes billions of mutual connections and intelligently identifies potential relations. Web vendors analyze millions of commodities such as news, products, and services to produce personalized recommendations for users. Financial and medical institutions launch millions of financial and medical record transactions in secure cloud databases per day. However, all of the above use cases involve a large amount of data accesses that are considered irregular or even random. Traditional computing platform architectures (e.g., CPUs and GPUs) have been shown to be inefficient for processing these data-intensive applications because (a) the large and irregular memory footprint renders the on-chip cache ineffective, (b) segmented and irregular cache line granularity accesses do not saturate the main memory bandwidth, and (c) the dataflow can be data dependent with frequent processor stalls. To advance data-intensive applications, there is a critical need to synergize new ideas in hardware, algorithms, and systems to efficiently execute these vital applications. This thesis proposes a series of works that optimizes the performance of executing a wide range of emerging data-intensive applications. Specifically, we combat the irregularity and randomness in these applications using different software-hardware co-designs. First, I propose Mint—a novel accelerator architecture and a programming model for mining temporal motifs in graphs of millions of nodes efficiently. Temporal motif mining is a fundamental problem used in a variety of complex systems, including social networks, financial markets, biology, and neuroscience. We show in this work that a decoupled dataflow execution programming model and specialized hardware can dramatically improve memory utilization and thus improve the temporal motif mining performance. Second, I present GRACE—a lightweight and scalable graph-based algorithm-system codesign framework to significantly improve the embedding layer performance of recommendation models that serve personalized recommendations of millions of items. Specifically, GRACE proposes a novel Item Co-occurrence Graph (ICG) and presents a new system-aware ICG clustering algorithm to find frequently accessed item combinations of arbitrary lengths to compute their partial sums. We use this work to show that we can find popular access patterns of combinations of arbitrary lengths in the recommendation systems to speed up the application. This leads to tremendous savings in the Total Cost of Ownership (TCO) and energy given the prevalence of this application. Lastly, I present Palermo—a protocol-hardware co-design to improve oblivious memory (ORAM) access performance. The security and privacy of outsourcing memory to the cloud are becoming increasingly important as cloud-based computing is on the rise. Maintaining the obliviousness of memory access comes with a huge amount of oblivious requests, making it data-intensive. We show in this work that Palermo re-architects the ORAM protocol and designs a novel hardware ORAM controller architecture to fully unlock the potential of our protocol. The design achieves significant performance speedup compared to the state-of-the- art baselines, with a negligible area overhead on a CPU, without compromising security.