Karl Taht's Research Paper Blog

Authors: Makhlouf Hadji, Djamal Zeghlache Venue:  ICCC 2012 (International Conference on Cloud Computing) This paper presents a cloud resource allocation formulated as a graph, which can be solved optimally by applying a min-cost, max flow algorithm. The exact formulation in previous work suffers from scalability due to its NP-hard formulation. In contrast, MCMF is itself a polynomial algorithm with exact correctness. The real magic of how this works is actually a subtlety which related bin-packing to max-flow. I am not 100% clear on exactly how this problem is reduced from an NP-hard assignment problem to a polynomial, but Google's OR-tools provides a decent high-level description: " How does the min cost flow problem above represent an assignment problem? First, since the capacity of every arc is 1, the supply of 4 at the source forces each of the four arcs leading into the workers to have a flow of 1. Next, the flow-in-equals-flow-out condition forces the flow out of...

Authors: Wenlin Chen, James T. Wilson, Stephen Tyree, Killian Q. Weinberger, Yixin Chen Venue: ICML 2015 Note: this is a brief summary as the read was brisk. The key idea of this paper is to reduce the memory footprint of weight matrices by using a hash table to store weights. Unlike typical hash tables which are much larger than the size of the data, these hash tables are actually much smaller than the original weight matrix. Collisions cause random weight sharing. Interestingly, this approach can be used during both training and inference. The results show that this approach outperforms low-rank matrix decomposition, random edge removal, an equivalent NN with the same size and in most cases Dark Knowledge (DK). In addition, their technique can be used in conjunction with DK, resulting in even better results. Another auxiliary benefit is that a network can be made arbitrarily larger (e.g. increasing the number of hidden nodes in a layer), while keep a fixed memory footprint. In t...

Authors: Archana Ganapathi, Kaushik Datta, Armando Fox, David Patterson Venue: USENIX Hot Topics in Parallelism 2009 This workshop paper examines applying a machine learning technique to auto-tuning HPC stencils. The configuration space consists of 5 independent knobs resulting in a total of ~4 million possible configurations. The work applies KCCA (kernel canonical correlation analysis) which finds correlations between two sets of data, in this case performance measurements and tune settings. KCCA is a specific way to do this that allows for non-linear relationships. Compared to feature extraction techniques, this is a direct way to find correlations rather than just using an intermediate step of feature extraction followed by a method of clustering. The main reason this appears to be only a workshop paper is that only two experiments are performed, both using stencils. The KCCA algorithm is definitely worth a deeper understanding, as the results are promising. Full Text

Authors: Dana Van Aken, Andrew Pavlo, Geoffrey J. Gordon, Bohan Zhang Venue:    SIGMOD 2017 The paper presented an automated framework for tuning database configuration knobs called OtterTune. OtterTune uses a hybrid of offline and online learning, which enables it to recognize similar behaviors and perform online optimization faster.       Before final optimization of a workload, a database of various knob settings and workloads must be collected. Next, OtterTune uses factor analysis to to first prune the set of performance metrics (a dimensionality reduction technique). Next performance tuning knobs are ranked via Lasso regularization. This allows for the automated tuner to reduce the search space by prioritizing the most impactful knobs.      Online, the OtterTune first tries to find a match between a previous workload and the current workload. The next phase is the exploration/exploitation phase which is guided by a Gaussian Process....