Convolutional Neural Networks (CNNs) achieve state-of-the-art performance for perception tasks at the cost of billions of computational operations. In this paper, we propose a probabilistic prediction processing syste...
详细信息
ISBN:
(纸本)9781450393225
Convolutional Neural Networks (CNNs) achieve state-of-the-art performance for perception tasks at the cost of billions of computational operations. In this paper, we propose a probabilistic prediction processing system, dubbed (PS)-S-3, to eliminate redundant compute-heavy convolution operations by predicting whether output activations are zero-valued. By exploiting the probability characteristic of Gaussian-like distributed activations and weights in CNNs, (PS)-S-3 calculates the partial convolution across values greater than a standard deviation-related threshold, to predict the ineffectual output activations. (PS)-S-3 skips remaining convolutions and sets outputs to zero in advance if output activations are predicted to be zero. (PS)-S-3 reduces 67% computations within 0.2% accuracy loss and does not even require retraining or fine-tuning CNNs. We further implement a (PS)-S-3-based CNN accelerator that achieves 2.02x speedup and 2.23x energy efficiency on average over the traditional accelerator. Compared with the state-of-the-art prediction-based accelerator with 3% accuracy degradation, our (PS)-S-3 yields up to 1.49x speedup and 1.69x energy efficiency.
distributed multi-writer atomic registers are at the heart of a large number of distributed algorithms. While enjoying the benefits of atomicity, researchers further explore fast implementations of atomic reigsters wh...
详细信息
ISBN:
(纸本)9781450375825
distributed multi-writer atomic registers are at the heart of a large number of distributed algorithms. While enjoying the benefits of atomicity, researchers further explore fast implementations of atomic reigsters which are optimal in terms of data access latency. Though it is proved that multi-writer atomic register implementations are impossible when both read and write are required to be fast, it is still open whether implementations are impossible when only write or read is required to be fast. This work proves the impossibility of fast write implementations based on a series of chain arguments among indistiguishable executions. We also show the necessary and sufficient condition for fast read implementations by extending the results in the single-writer case. This work concludes a series of studies on fast implementations of distributed atomic registers.
A set of participants that want to agree on a common opinion despite the presence of malicious or Byzantine participants need to solve an instance of a Byzantine agreement problem. This classic problem has been well s...
详细信息
ISBN:
(纸本)9781450375825
A set of participants that want to agree on a common opinion despite the presence of malicious or Byzantine participants need to solve an instance of a Byzantine agreement problem. This classic problem has been well studied but most of the existing solutions assume that the participants are aware of n - the total number of participants in the system - and f - the upper bound on the number of Byzantine participants. In this paper, we examine a synchronous system with Byzantine faults where the participants are neither aware of n nor f. The participants have unique identifiers, which are not necessarily consecutive. For such a system, we give algorithms for rotor-coordinator and consensus, both with the resiliency of n > 3f, which is also the optimal resiliency for solving consensus when the participants know n and f. Thus, resiliency is unaffected even if the Byzantine participants can lie about n and f.
The proceedings contain 56 papers. The topics discussed include: affecting user’s self-esteem: analysis under the self-determination theory perspective and design recommendations;analysis and convergence of stu...
ISBN:
(纸本)9781450386173
The proceedings contain 56 papers. The topics discussed include: affecting user’s self-esteem: analysis under the self-determination theory perspective and design recommendations;analysis and convergence of studies on recommendations for digital memorials;analysis of the user experience with a multiperspective tool for explainable machine learning in light of interactive principles;analytical model for classifying areas of interest in interactive systems;analyzing the presentation of multilingual user reviews in accommodation websites;applying usability heuristics in the context of labeling systems;beyond barriers: a practical analysis of the SIM-SR method to inspect the communicability of interactive systems for visually impaired users;building an iot programming environment with and for preschool children;and challenges of interaction design for counter-hegemonic contexts: highlighting and overcoming contradictions for social transformation and responsiveness.
Much progress has recently been made in understanding the complexity landscape of subgraph finding problems in the CONGEST model of distributedcomputing. However, so far, very few tight bounds are known in this area....
详细信息
ISBN:
(纸本)9781611976465
Much progress has recently been made in understanding the complexity landscape of subgraph finding problems in the CONGEST model of distributedcomputing. However, so far, very few tight bounds are known in this area. For triangle (i.e., 3-clique) listing, an optimal (O) over tilde (n(1/3))-round distributed algorithm has been constructed by Chang et al. [SODA 2019, PODC 2019]. Recent works of Eden et al. [DISC 2019] and of Censor-Hillel et al. [PODC 2020] have shown sublinear algorithms for K-p-listing, for each p >= 4, but still leaving a significant gap between the upper bounds and the known lower bounds of the problem. In this paper, we completely close this gap. We show that for each p >= 4, there is an (O) over tilde (n(1-2/p))-round distributed algorithm that lists all p-cliques K-p in the communication network. Our algorithm is optimal up to a polylogarithmic factor, due to the (Omega) over tilde (n(1-2/p))-round lower bound of Fischer et al. [SPAA 2018], which holds even in the CONGESTED CLIQUE model. Together with the trianglelisting algorithm by Chang et al. [SODA 2019, PODC 2019], our result thus shows that the round complexity of K-p-listing, for all p, is the same in both the CONGEST and CONGESTED CLIQUE models, at (Theta) over tilde (n(1-2/p)) rounds. For p = 4, our result additionally matches the (Omega) over tilde (n(1/2)) lower bound for K-4 -detection by Czumaj and Konrad [DISC 2018], implying that the round complexities for detection and listing of K-4 are equivalent in the CONGEST model.
Locally checkable labeling problems (LCLs) are distributed graph problems in which a solution is globally feasible if it is locally feasible in all constant-radius neighborhoods. Vertex colorings, maximal independent ...
详细信息
ISBN:
(纸本)9781450375825
Locally checkable labeling problems (LCLs) are distributed graph problems in which a solution is globally feasible if it is locally feasible in all constant-radius neighborhoods. Vertex colorings, maximal independent sets, and maximal matchings are examples of LCLs. On the one hand, it is known that some LCLs benefit exponentially from randomness-for example, any deterministic distributed algorithm that finds a sinkless orientation requires Theta(logn) rounds in the LOCAL model, while the randomized complexity of the problem is Theta(log logn) rounds. On the other hand, there are also many LCLs in which randomness is useless. Previously, it was not known whether there are any LCLs that benefit from randomness, but only subexponentially. We show that such problems exist: for example, there is an LCL with deterministic complexity Theta(log(2) n) rounds and randomized complexity T(logn log logn) rounds.
This paper considers the problem of Byzantine fault-tolerance in distributed multi-agent optimization. In this problem, each agent has a local cost function. The goal of a distributed optimization algorithm is to allo...
详细信息
ISBN:
(纸本)9781450375825
This paper considers the problem of Byzantine fault-tolerance in distributed multi-agent optimization. In this problem, each agent has a local cost function. The goal of a distributed optimization algorithm is to allow the agents to collectively compute a minimum of their aggregate cost function. We consider the case when a certain number of agents may be Byzantine faulty. Such faulty agents may not follow a prescribed algorithm, and they may send arbitrary or incorrect information regarding their local cost functions. Unless a fault-tolerance mechanism is employed, traditional distributed optimization algorithms cannot tolerate such faulty agents. A reasonable goal in presence of faulty agents is to minimize the aggregate cost of the non-faulty agents. However, we show that this goal is impossible to achieve unless the cost functions of the non-faulty agents have a minimal redundancy property. We further propose a distributed optimization algorithm that allows the non-faulty agents to obtain a minimum of their aggregate cost if the minimal redundancy property holds. The scope of our algorithm is demonstrated through distributed sensing and learning applications, which are special cases of distributed optimization.
The Lovász Local Lemma is a versatile result in probability theory, characterizing circumstances in which a collection of n ‘bad events’, each occurring with probability at most p and dependent on a set of unde...
详细信息
ISBN:
(纸本)9798400715105
The Lovász Local Lemma is a versatile result in probability theory, characterizing circumstances in which a collection of n ‘bad events’, each occurring with probability at most p and dependent on a set of underlying random variables, can be avoided. It is a central tool of the probabilistic method, since it can be used to show that combinatorial objects satisfying some desirable properties must exist. While the original proof was existential, subsequent work has shown algorithms for the Lovász Local Lemma: that is, in circumstances in which the lemma proves the existence of some object, these algorithms can constructively find such an object. One main strand of these algorithms, which began with Moser and Tardos’s well-known result (Jacm 2010), involves iteratively resampling the dependent variables of satisfied bad events until none remain *** this paper, we present a novel analysis that can be applied to resampling-style Lovász Local Lemma algorithms. This analysis shows that an output assignment for the dependent variables of most events can be determined only from O(loglog1/p n)-radius local neighborhoods, and that the events whose variables may still require resampling can be identified from these neighborhoods. This allows us to improve randomized complexities for the constructive Lovász Local Lemma (with polynomial criterion) in several parallel and distributed *** particular, we obtain a LOCAL algorithm with O(loglog1/p n) node-averaged complexity (while matching the O(log1/p n) worst-case complexity of Chung, Pettie, and Su), an algorithm for the LCA and VOLUME models requiring dO(loglog1/p n) probes per query, and an O(logloglog1/p n)-round algorithm for the CONGESTED CLIQUE, linear space MPC, and Heterogenous MPC models.
Most CS1 classes are designed to teach programming and computational thinking using a specific programming language such as Python or Java. This type of in-depth study leaves little room for creative exploration by st...
详细信息
ISBN:
(纸本)9798400704246
Most CS1 classes are designed to teach programming and computational thinking using a specific programming language such as Python or Java. This type of in-depth study leaves little room for creative exploration by students. In particular, at large colleges and universities, the programming assignments are usually autograded to keep up with expanding enrollment. This lightning talk will introduce the idea that simply adding three creative labs that do not use the actual course material, but instead expose students to other computing concepts, can give the students who are struggling a chance to catch up, while also offering them a much-needed breather doing something in computing that is individually directed and *** the last few years, my Teaching Assistants (TAs) and I have developed three simple web development labs as assignments for our large CS1 classes. These three labs are usually given around each of the exam weeks and provide a much-needed break for the students from the regular class material that continues to build upon prior learning. Many students report that the labs were their favorite part of the course because they were creative and *** lightning talk aims to gather feedback on this concept and assess its potential for integration into advanced CS courses. I'm also keen to hear suggestions for alternative labs in a CS1 class that would both introduce students to further CS principles and allow them to showcase their creativity.
暂无评论