We present a new approach to the minimum-cost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multivariate polynomials over a finite field of characteristic two for no...
详细信息
We present a new approach to the minimum-cost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multivariate polynomials over a finite field of characteristic two for non-identity with zero. In effect, we show that a minimum-cost flow of value k in a network with n vertices, a sink and a source, integral edge capacities and positive integral edge costs polynomially bounded in n can be found by a randomized PRAM, with errors of exponentially small probability in n, running in O(klog(kn)+log(2)(kn)) time and using 2 (k) (kn) (O(1)) processors. Thus, in particular, for the minimum-cost flow of value O(logn), we obtain an RNC2 algorithm, improving upon time complexity of earlier NC and RNC algorithms.
Computer architecture courses typically include lab sessions to reinforce, from a practical perspective, concepts and architectural mechanisms studied in lectures. Lab sessions are mainly based on simulation framework...
详细信息
Computer architecture courses typically include lab sessions to reinforce, from a practical perspective, concepts and architectural mechanisms studied in lectures. Lab sessions are mainly based on simulation frameworks because they benefit learning. Reading the source code that models certain processor mechanisms allows students to acquire a sound knowledge of how hardware works. Unfortunately, simulators that model current multicore processors are getting more and more complex, which lengthens the learning phase and complicates their use in time-bounded lab sessions. In this paper, we propose a new approach that complements the use of simulation frameworks in lab sessions of computer architecture courses. This approach is based on performing experiments on current commercial processors, where multiple hardware events related to the performance of the computer components under study are monitored. Then, students analyze the measured events and how they impact the overall performance. Such analysis motivates students and, not only helps reinforcing the theoretical concepts, but also increases their analysis skills. In this paper we present the methodology and scheduling framework that support the proposed approach and discuss five lab sessions, which can be applied in different courses, covering multiple computer architecture topics. (C) 2018 Elsevier Inc. All rights reserved.
Given a set of functional dependencies Σ and a single dependency σ, we show that the algorithm to test whether Σ implies σ is log-space complete in P. The functional dependencies Σ are represented as a directed h...
详细信息
ISBN:
(纸本)0818620528
Given a set of functional dependencies Σ and a single dependency σ, we show that the algorithm to test whether Σ implies σ is log-space complete in P. The functional dependencies Σ are represented as a directed hypergraph HΣ [1]. We first present a parallel algorithm which solves the above implication problem using P processors on a EREW-PRAM in Ο(e/P + ***) time and on a CRCW-PRAM in Ο(e/P + n) time, where e and n are the number of arcs and nodes of the graph HΣ. For graphs HΣ with fixed degree and diameter, we show that the closure HΣ+ can be computed in NC. We present NC algorithms to obtain a non-redundant and a LR-Minimum cover for the set of functional dependencies Σ. All our algorithms on a n-node directed hypergraph with fixed degree and diameter can be implemented to run in Ο(log2n) time with M(n) processors on a CREW-PRAM model, where M(n) is the cost of multiplying two binary matrices. The algorithms are efficient based on the transitive closure bottleneck phenomenon [7] that is, any improvement in the time and processor complexity of the transitive closure algorithm will result in an improvement by the same amount for the algorithms presented here.
暂无评论