- talks - lists.cs.princeton.edu

Caleb Levy will present his FPO "New Paths from Splay to Dynamic Optimality" on Wednesday, May 15, 2019 at 2pm in Fine Hall 224
by Nicki Mahler 13 May '19

13 May '19

Caleb Levy will present his FPO "New Paths from Splay to Dynamic Optimality" on Wednesday, May 15, 2019 at 2pm in Fine Hall 224. The members of his committee are as follows: Advisor: Robert Tarjan Non-Readers: Bernard Chazelle and Robert Sedgewick Readers: Kurt Mehlhorn ( Max-Planck-Institut fur Informatik) Abstract: Consider the task of performing a sequence of searches in a binary search tree. After each search, an algorithm is allowed to arbitrarily restructure the tree, at a cost proportional to the amount of restructuring performed. The cost of an execution is the sum of the time spent searching and the time spent optimizing those searches with restructuring operations. This notion was introduced by Sleator and Tarjan in 1985, along with an algorithm and a conjecture. The algorithm, Splay, is an elegant procedure for performing adjustments while moving searched items to the top of the tree. The conjecture, called dynamic optimality, is that the cost of splaying is always within a constant factor of the optimal algorithm for performing searches. The conjecture stands to this day. We make the following contributions to this problem: 1. We introduce simulation embeddings: mappings from executions to lists of keys that induce target algorithms to simulate the executions. We build a simulation embedding for Splay by inducing Splay to perform arbitrary subtree transformations, and show that if the cost of splaying a sequence of items is an upper bound on the cost of splaying every subsequence thereof to within a constant factor, then Splay is dynamically optimal. We call this property approximate monotonicity. We also show that approximate monotonicity is a necessary condition for dynamic optimality. 2. We show that if Splay is dynamically optimal, then with respect to optimal costs, its additive overhead is at most linear in the sum of initial tree size and number of requests. 3. We prove that Wilber’s lower bound on optimal execution cost is approximately monotone. 4. Drawing on extensive empirical and heuristic observations, we speculate about how one might establish dynamic optimality by adapting the proof of monotonicity from the crossing lower bound to Splay. 5. We show that several related conjectures also follow if Splay is approximately monotone, and demonstrate that most of the results in this paper extend to a broader class of “path-based” algorithms. It is hoped that this work lays the foundations for a final proof of the dynamic optimality conjecture. A copy of this thesis is available upon request.

1 0

Reminder: Jishen Zhao tomorrow at 12:30
by Emily C. Lawrence 13 May '19

13 May '19

Prof. Jishen Zhao from University of California, San Diego Tuesday, May 14 at 12:30pm Computer Science - Room 105 [ https://www.cs.princeton.edu/events/25852 | https://www.cs.princeton.edu/events/25852 ] System and Architecture Design for Safe and Reliable Autonomous Robotic Applications The rapid development of smart technology in edge computing systems has paved the way for us to embrace the technology movement of self-driving cars and autonomous service robots. To enable the wide adoption of these autonomous robotic applications, reliability is one of fundamental goals of computing system and architecture design. In this talk, I will present our recent exploration of safe and reliable system and architecture design for autonomous robotic applications. I will start by presenting an architecture design of supporting fast system recovery with persistent memory at low performance cost. To evaluate and guide our system design, I will introduce our safety model and architecture design strategies for self-driving cars, based on our field study of running real industrial Level-4 autonomous driving fleets. Finally, I will describe a Linux-container-based resource management framework design to improve reliability and safety of self-driving cars and service robots. Bio: Jishen Zhao is an Assistant Professor in the Computer Science and Engineering Department at University of California, San Diego. Her research spans and stretches the boundary between computer architecture and system software, with a particular emphasis on memory and storage systems, domain-specific acceleration, and system reliability. Her research is driven by both emerging technologies (e.g., nonvolatile memories, 3D-stacked memory) and modern applications (e.g., smart home and autonomous robotic systems, deep learning, and big-data analytics). Before joining UCSD, she was an Assistant Professor at UC Santa Cruz, and a research scientist at HP Labs before joining UCSC. She is a recipient of NSF CAREER award and a MICRO best paper honorable mention award.

1 0

Wei Zhan will present his General Exam "Time-space tradeoff for memory game and random input model"on Monday, May 20, 2019 at 1pm in CS 401.
by Nicki Mahler 10 May '19

10 May '19

Wei Zhan will present his General Exam "Time-space tradeoff for memory game and random input model"on Monday, May 20, 2019 at 1pm in CS 401. BQ_BEGIN The members of his committee are as follows: Ran Raz (adviser), Gillat Kol, and Mark Braverman. BQ_END BQ_BEGIN Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. BQ_END BQ_BEGIN Abstract: In many natural problems, one can trade space for time by saving intermediate results, or vice versa by recomputing them. We examine this time-space tradeoff phenomenon in the following two specific problems: Memory game. The objective is to match n pairs of cards where you can only reveal one at a time. We resolve the two open questions left in [Chakrabarti & Chen, 2017] and obtain the tight time-spaces tradeoffs for the memory game: TS=Θ(n^2) in equality query model, and T^2S=Θ(n^3) for general randomized branching programs. Parity in random input model. We purpose this new model where in every step a uniformly random index is given, along with the input bit at this index. If some restricted dependencies are allowed among the inputs, any lower bound under this model will give a lower bound for oblivious branching programs. We show a tight TS=Θ(n^2) bound for computing pairty under this model with a special type of branching programs. Reading List: Textbook: Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach Papers: Paul Beame, Michael Saks, Xiaodong Sun, and Erik Vee. Time-space tradeoff lower bounds for randomized computation of decision problems. László Babai, Noam Nisan and Márió Szegedy. Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs Ran Raz. Fast learning requires good memory: A time-space lower bound for parity learning Sumegha Garg, Ran Raz and Avishay Tal. Extractor-Based Time-Space Lower Bounds for Learning Allan Borodin and Stephen A. Cook. A time-space tradeoff for sorting on a general sequential model of computation P. Beame, R. Clifford, and W. Machmouchi. Element Distinctness, Frequency Moments, and Sliding Windows Amit Chakrabarti, Yining Chen. Time-Space Tradeoffs for the Memory Game Lance Fortnow. Time-Space Tradeoffs for Satisfiability Dylan McKay and Ryan Williams. Quadratic Time-Space Lower Bounds for Computing Natural Functions With a Random Oracle BQ_END

1 0

Prakash Murali will present his General Exam "Full-Stack, Real-System Quantum Computer Studies: Noise-Adaptive Compilation, Technology Comparisons and Architectural Insights" on Tuesday, May 21, 2019 at 9am in CS 401.
by Nicki Mahler 10 May '19

10 May '19

Prakash Murali will present his General Exam "Full-Stack, Real-System Quantum Computer Studies: Noise-Adaptive Compilation, Technology Comparisons and Architectural Insights" on Tuesday, May 21, 2019 at 9am in CS 401. The members of his committee are as follows: Margaret Martonosi (adviser), Kyle Jamieson, and Frederic T. Chong (University of Chicago) Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Abstract: In recent years, Quantum Computing (QC) has progressed to the point where small working prototypes are available for use. Termed Noisy Intermediate-Scale Quantum (NISQ) computers, these prototypes are too small for large benchmarks or even for Quantum Error Correction (QEC), but they do have sufficient resources to run small benchmarks, particularly if compiled with optimizations to make use of scarce qubits and limited operation counts and coherence times. First, we observe that current QC prototypes have large spatial and temporal fluctuations in qubit noise and operation error rates. Leveraging this observation, we propose and evaluate noise-adaptive backend compiler approaches to map and optimize high-level QC programs to execute with high reliability on NISQ systems. Using real-system measurements, we show that fine-grained spatial and temporal variations of hardware noise parameters can be exploited to obtain an average 2.9x (and up to 18x) improvement in program success rate over the IBM Qiskit compiler, which is the default compiler on IBM’s quantum systems. Second, we perform a full-stack, benchmark-driven hardware-software analysis of QC systems. We evaluate QC hardware possibilities (qubit types, connectivity, noise), software-visible gates (ISA), and software optimizations to tackle fundamental design choices for the execution stack. To enable our study, we built TriQ, the first top-to-bottom toolflow to target different qubit device technologies, including superconducting and trapped ion qubits which are the current QC front-runners. We use TriQ to conduct real-system measurements on 6 QC systems from three different groups, IBM, Rigetti, and University of Maryland. We draw conclusions about gate set design, factors affecting program performance and compiler optimizations to mitigate hardware limitations. We demonstrate that leveraging microarchitecture details in the compiler improves program success rate up to 28x on IBM (geomean 3x), 2.3x on Rigetti (geomean 1.4x), and 1.47x on UMD (geomean 1.17x), compared to respective vendor toolflows. Reading List Muhamamd Ahsan, Byung-Soo Choi, Jungsang Kim. Performance simulator based on hardware resources constraints for ion trap quantum computer. IEEE International Conference on Computer Design (ICCD) 2013 David P. DiVincenzo. The Physical Implementation of Quantum Computation. Fortschritte der Physik 48, p. 771 (2000) arXiv:quant-ph/0002077 Richard Feynman. Simulating physics with computers. International Journal of Theoretical Physics, Vol 21, Nos. 6/7, 1982. X. Fu, M. A. Rol, C. C. Bultink, J. van Someren, N. Khammassi, I. Ashraf, R. F. L. Vermeulen, J. C. de Sterke, W. J. Vlothuizen, R. N. Schouten, C. G. Almudever, L. DiCarlo, K. Bertels. An Experimental Microarchitecture for a Superconducting Quantum Processor. MICRO-50 (2017) Lov Grover. A fast quantum mechanical algorithm for database search. ACM Symposium on the Theory of Computing (STOC) 1996. Ali Javadi-Abhari, Pranav Gokhale, Adam Holmes, Diana Franklin, Ken Brown, Margaret Martonosi, and Frederic T. Chong. Optimized Surface Code Communication in Superconducting Quantum Computers, International Symposium on Microarchitecture, 2017 Ali Javadi-Abhari, Shruti Patil, Daniel Kudrow, Jeff Heckey, Alexey Lvov, Frederic T. Chong, Margaret Martonosi. ScaffCC: A Framework for Compilation and Analysis of Quantum Computing Programs. ACM International Conference on Computing Frontiers, May 2014. Jeff Heckey, Shruti Patil, Ali Javadi-Abhari, Adam Holmes, Daniel Kudrow, Ken Brown, Diana Franklin, Margaret Martonosi, Frederic T. Chong. Compiler Management of Communication and Parallelism for Quantum Computation. Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2015. Norbert M. Linke, Dmitri Maslov, Martin Roetteler, Shantanu Debnath, Caroline Figgatt, Kevin A. Landsman, Kenneth Wright, and Christopher Monroe. Experimental comparison of two quantum computing architectures. PNAS 114, 3305-3310 (2017) Tony Nowatzki, Michael Sartin-Tarm, Lorenzo De Carli, Karthikeyan Sankaralingam, Cristian Estan, Behnam Robatmili.. A general constraint-centric scheduling framework for spatial architectures. PLDI 2013: 495-506 Marcos Yukio Siraichi, Vinícius Fernandes dos Santos, Sylvain Collange, Fernando Magno Quintao Pereira. Qubit allocation. International Symposium on Code Generation and Optimization (CGO) 2018 Krysta M. Svore, Igor L. Markov, Isaac Chuang, Andrew W. Cross, Alfred V. Aho. A Layered Software Architecture for Quantum Computing Design Tools. IEEE Computer (Volume: 39, Issue: 1, Jan. 2006) Textbook: John L. Hennessy and David A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann 5th edition (2011).

1 0

Sachin Ravi will present his FPO "Meta-Learning for Data and Processing Efficiency" on Friday, 5/17/2019 at 10 AM in CS 402
by Nicki Mahler 10 May '19

10 May '19

Sachin Ravi will present his FPO "Meta-Learning for Data and Processing Efficiency" on Friday, 5/17/2019 at 10 AM in CS 402. The members of his committee are as follows: Kai Li (adviser) Nonreaders: Jonathan Cohen and Jia Deng; Readers: Karthik Narasimhan and Hugo Larochelle (Google Brain, University of Montreal) All are welcome to attend. A copy of his thesis is available in CS 310. His abstract follows below. Deep learning models have shown great success in a variety of machine learning benchmarks; however, these models still lack the eciency and flexibility of humans. Current deep learning methods involve training on a large amount of data to produce a model that can then specialize to the specific task encoded by the training data. Humans, on the other hand, are able to learn new concepts throughout our lives with comparatively little feedback. In order to bridge this gap, previous work has suggested the use of meta-learning. Rather than learning how to do a specific task, meta-learning involves learning how-to-learn and utilizing this knowledge to learn new tasks more e↵ectively. This thesis focuses on using meta-learning to improve the data and processing eciency of deep learning models when learning new tasks. First, we discuss a meta-learning model for the few-shot learning problem, where the aim is to learn a new classification task having unseen classes with few labeled examples. We use a LSTM-based meta-learner model to learn both the initialization and the optimization algorithm used to train another neural network and show that our method compares favorably to nearest-neighbor approaches. The second part of the thesis deals with improving the predictive uncertainty of models in the few-shot learning setting. Using a Bayesian perspective, we propose a meta-learning method which eciently amortizes hierarchical variational inference across tasks, learning a prior distribution over neural network weights so that a few steps of gradient descent will produce a good task-specific approximate posterior. Finally, we focus on applying meta-learning in the context of making choices that impact processing ecacy. When training a network on multiple tasks, we have a choice between interactive parallelism (training on di↵erent tasks one after another) and independent parallelism (using the network to process multiple tasks concurrently). For the simulation environment considered, we show that there is a trade-o↵ between these two types of processing choices in deep neural networks. We then discuss a meta-learning algorithm for an agent to learn how to train itself with regard to this trade-o↵ in an environment with unknown serialization cost.

1 0

Colloquium Speaker Jishen Zhao, Tuesday, May 14
by Emily C. Lawrence 08 May '19

08 May '19

Prof. Jishen Zhao from University of California, San Diego Tuesday, May 14 at 12:30pm Computer Science - Room 105 [ https://www.cs.princeton.edu/events/25852 | https://www.cs.princeton.edu/events/25852 ] System and Architecture Design for Safe and Reliable Autonomous Robotic Applications The rapid development of smart technology in edge computing systems has paved the way for us to embrace the technology movement of self-driving cars and autonomous service robots. To enable the wide adoption of these autonomous robotic applications, reliability is one of fundamental goals of computing system and architecture design. In this talk, I will present our recent exploration of safe and reliable system and architecture design for autonomous robotic applications. I will start by presenting an architecture design of supporting fast system recovery with persistent memory at low performance cost. To evaluate and guide our system design, I will introduce our safety model and architecture design strategies for self-driving cars, based on our field study of running real industrial Level-4 autonomous driving fleets. Finally, I will describe a Linux-container-based resource management framework design to improve reliability and safety of self-driving cars and service robots. Bio: Jishen Zhao is an Assistant Professor in the Computer Science and Engineering Department at University of California, San Diego. Her research spans and stretches the boundary between computer architecture and system software, with a particular emphasis on memory and storage systems, domain-specific acceleration, and system reliability. Her research is driven by both emerging technologies (e.g., nonvolatile memories, 3D-stacked memory) and modern applications (e.g., smart home and autonomous robotic systems, deep learning, and big-data analytics). Before joining UCSD, she was an Assistant Professor at UC Santa Cruz, and a research scientist at HP Labs before joining UCSC. She is a recipient of NSF CAREER award and a MICRO best paper honorable mention award.

1 0

Udaya Ghai will present his MSE thesis talk "Exponentiated Gradient Meets Gradient Descent" on May 13th, 2019 at 12:30pm in CS 402.
by Nicki Mahler 07 May '19

07 May '19

Udaya Ghai will present his MSE thesis talk "Exponentiated Gradient Meets Gradient Descent" on May 13th, 2019 at 12:30pm in CS 402. The members of his committee are Elad Hazan and Yoram Singer. Everyone is invited to attend his/her talk. His abstract follows below. Abstract: The (stochastic) gradient descent and the multiplicative update method are probably the most popular algorithms in machine learning. We introduce and study a new regularization which provides a unification of the additive and multiplicative updates. This regularization is derived from an hyperbolic analogue of the entropy function, which we call hypentropy. It is motivated by a natural extension of the multiplicative update to negative numbers. The hypentropy has a natural spectral counterpart which we use to derive a family of matrix-based updates that bridge gradient methods and the multiplicative method for matrices. While the latter is only applicable to positive semi-definite matrices, the spectral hypentropy method can naturally be used with general rectangular matrices. We analyze the new family of updates by deriving tight regret bounds. We study empirically the applicability of the new update for settings such as multiclass learning, in which the parameters constitute a general rectangular matrix.

1 1

Zhenyu Song will present his General Exam "Robustly Improving Byte Miss Ratio with Workload-Learning Caching" on Tuesday, May 21, 2019 at 2pm in CS 402.
by Nicki Mahler 07 May '19

07 May '19

Zhenyu Song will present his General Exam "Robustly Improving Byte Miss Ratio with Workload-Learning Caching" on Tuesday, May 21, 2019 at 2pm in CS 402. The members of his committee are as follows: Kai Li (adviser), Wyatt Lloyd, and Ryan Adams Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Abstract : Content Distribution Networks (CDNs) made up of widely-distributed caches deliver the majority of bytes sent across the Internet. Their efficiency and cost-effectiveness directly correspond to the byte miss ratio achieved by their caches. Improving the byte miss ratio across the many caches in a CDN is hampered by the diversity of workloads resulting in no one current algorithm being best in all cases. We introduce the workload-learning caching (WLC) algorithm that robustly improves byte miss ratio. WLC is robust because its model and feature set allow it to make decisions using a superset of the information used in current algorithms. WLC improves byte miss ratio by learning from a workload and adapts to recent request patterns dynamically. Simulation results using 3 CDN traces and 3 other traces with a wide range of cache sizes show that WLC robustly improves byte miss ratio over the state of the art algorithms. We have implemented WLC in a CDN caching proxy. Our experiments show that it provides lower byte miss ratios while achieving throughput and latency similar to the baseline. It requires moderate moderate amount of CPU power and relatively small memory overhead in today's CDN server without GPU or accelerators. Book : Distributed Systems: Principles and Paradigms . Andrew S. Tanenbaum and Maaten Van Steen. Papers: 1. Belady, Laszlo A. "A study of replacement algorithms for a virtual-storage computer." IBM Systems journal 5.2 (1966): 78-101. 2. Breslau, Lee, et al. "Web caching and Zipf-like distributions: Evidence and implications." INFOCOM'99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. Vol. 1. IEEE, 1999. 3. Cao, Pei, and Sandy Irani. "Cost-Aware WWW Proxy Caching Algorithms."Usenix symposium on internet technologies and systems. Vol. 12. No. 97. 1997. 4. Megiddo, Nimrod, and Dharmendra S. Modha. "ARC: A Self-Tuning, Low Overhead Replacement Cache." FAST. Vol. 3. No. 2003. 2003. 5. Beckmann, Nathan, Haoxian Chen, and Asaf Cidon. "LHD: Improving Cache Hit Rate by Maximizing Hit Density." 15th USENIX Symposium on Networked Systems Design and Implementation (NSDI 18). 2018 6. Vietri, Giuseppe, et al. "Driving cache replacement with ml-based lecar." 10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage 18). 2018. 7. Nygren, Erik, Ramesh K. Sitaraman, and Jennifer Sun. "The akamai network: a platform for high-performance internet applications." ACM SIGOPS Operating Systems Review 44.3 (2010): 2-19. 8. Tang, Linpeng, et al. "Popularity prediction of facebook videos for higher quality streaming." 2017 USENIX Annual Technical Conference (USENIX ATC 17). 2017. 9. Hashemi, Milad, et al. "Learning Memory Access Patterns." International Conference on Machine Learning. 2018. 10. Friedman, Jerome H. "Greedy function approximation: a gradient boosting machine." Annals of statistics (2001): 1189-1232.

1 0

Theano Stavrinos will present her general exam on May 22, 2019 at 10am in CS 402
by Nicki Mahler 07 May '19

07 May '19

Theano Stavrinos will present her general exam on May 22, 2019 at 10am in CS 402. The members of her committee are: Wyatt Lloyd (adviser), Amit Levy, and Jennifer Rexford Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. Abstract: Centralized sequencers are an increasingly common tool for ordering events in a distributed system due to their simplicity and high performance relative to distributed ordering protocols. However, as centralized, on-path components, sequencers present challenges to designers of high-performance systems. First, the throughput of the entire system is limited by the performance of the sequencer. Second, packet loss and component failures may lead to holes (gaps) in the sequence; holes are difficult to deal with at the system level without affecting performance. This generals exam describes the CATS project, which designs and implements a sequencing subsystem that addresses these issues. The main components of CATS are a sequencer recovery protocol; a proxy layer which requests sequence numbers and executes operations on behalf of clients; and a reliable transport protocol, TCATS, tailored to the CATS subsystem. These components work together to provide sequencing with unbounded throughput, meanwhile presenting to clients the simple abstraction of a holeless sequence. This exam will also present an evaluation of TCATS, the custom transport protocol, alongside other reliable transport protocols to determine whether TCATS is necessary for the good performance of the sequencing subsystem. -------------- Textbook: “Distributed Systems” by Tanenbaum and van Steen Datacenter networking/RPC-related papers 1. Kalia, Anuj, Michael Kaminsky, and David G. Andersen. “ Datacenter RPCs can be General and Fast. ” In Proc. USENIX NSDI. 2019. (eRPC) 2. Jeong, EunYoung, Shinae Wood, Muhammad Jamshed, Haewon Jeong, Sunghwan Ihm, Dongsu Han, and KyoungSoo Park. " mTCP: a Highly Scalable User-level TCP Stack for Multicore Systems. " In 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14), pp. 489-502. 2014. 3. Birrell, Andrew D., and Bruce Jay Nelson. " Implementing remote procedure calls. " ACM Transactions on Computer Systems (TOCS) 2, no. 1 (1984): 39-59. 4. Montazeri, Behnam, Yilong Li, Mohammad Alizadeh, and John Ousterhout. " Homa: A receiver-driven low-latency transport protocol using network priorities. " In Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication, pp. 221-235. ACM, 2018. Papers related to ordering of events in distributed systems 1. Lamport, Leslie. " Time, clocks, and the ordering of events in a distributed system. " Communications of the ACM 21, no. 7 (1978): 558-565. 2. Lamport, Leslie. " The part-time parliament. " ACM Transactions on Computer systems 16, no. 2 (1998): 133-169. 3. Herlihy, Maurice P., and Jeannette M. Wing. " Linearizability: A correctness condition for concurrent objects. " ACM Transactions on Programming Languages and Systems (TOPLAS) 12, no. 3 (1990): 463-492. 4. Corbett, James C., Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, Jeffrey John Furman, Sanjay Ghemawat et al. " Spanner: Google’s globally distributed database. " ACM Transactions on Computer Systems (TOCS) 31, no. 3 (2013): 8. 5. Wang, Cheng, Jianyu Jiang, Xusheng Chen, Ning Yi, and Heming Cui. " APUS: Fast and scalable Paxos on RDMA. " In Proceedings of the 2017 Symposium on Cloud Computing, pp. 94-107. ACM, 2017. Sequencer-related papers 1. Balakrishnan, Mahesh, Dahlia Malkhi, Vijayan Prabhakaran, Ted Wobbler, Michael Wei, and John D. Davis. " CORFU: A Shared Log Design for Flash Clusters. " In NSDI 12, pp. 1-14. 2012. 2. Li, Jialin, Ellis Michael, Naveen Kr Sharma, Adriana Szekeres, and Dan RK Ports. " Just Say NO to Paxos Overhead: Replacing Consensus with Network Ordering. " In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16), pp. 467-483. 2016. BQ_BEGIN BQ_END

1 0

Mina Tahmasbi Arashloo will present her FPO "Stateful Programming of High-Speed Network Hardware" on Thursday, 5/16/2019 at 1:30pm, in CS 401
by Nicki Mahler 07 May '19

07 May '19

Mina Tahmasbi Arashloo will present her FPO "Stateful Programming of High-Speed Network Hardware" on Thursday, 5/16/2019 at 1:30pm, in CS 401. The members of her committee are Jennifer Rexford (adviser); Readers: David Walker and Arvind Krishnamurthy (University of Washington); Nonreaders: Nick Feamster and Michael Freedman. A copy of her thesis, is available upon request. Everyone is invited to attend her talk. The talk title and abstract follow below: Modern networks need to operate at speeds as high as 100Gbps while running sophisticated algorithms and protocols to provide strict performance, security and reliability guarantees. Moreover, they need to flexibly adapt to the rapidly evolving requirements of online services. Thus, emerging network hardware devices, i.e. switches inside the network and Network Interface Cards (NICs) at the end hosts, are high-speed and programmable, with on-chip memory accessible on a per-packet basis to support stateful packet processing. However, the programming interfaces of these devices are quite low-level, tied to each device's architecture, and only suitable for programming a single device. Thus, programming collections of stateful network devices to realize a local or network-wide functionality efficiently and correctly is extremely difficult and error-prone. This dissertation focuses on the design and implementation of high-level programming abstractions for stateful programming of high-speed network hardware, both at the end hosts and inside the network. At the end host, we focus on the transport layer, the most complicated, constantly-evolving, and stateful component of the network stack. Transport-layer algorithms maintain state across packets to decide what data segments to transmit and when, and are notoriously difficult to implement on programmable NICs at high-speed. We propose Tonic, a hardware architecture for transport algorithms that can support 100Gbps for 128-byte packets while being programmable with a simple API. In designing Tonic, we exploit common patterns across transport algorithms to create efficient fixed-function reusable hardware modules, thus significantly reducing the functionality programmers must specify. To facilitate network-wide stateful programming, we propose SNAP, a programming language that abstracts the entire network as "one big stateful switch". Using SNAP, operators can program using persistent arrays on one big switch without deciding how to distribute and access them in the network's switches. The SNAP compiler discovers read/write dependencies between arrays, translates one-big-switch programs into an efficient internal representation based on binary decision diagrams, and uses it to jointly optimize array placement and routing across the network. All in all, Tonic's modular interface and SNAP's one-big-stateful-switch abstraction relieve programmers from the low-level details of stateful programming of high-speed network hardware throughout the entire network.

1 0