1,720,974 research outputs found
Nancy: An efficient parallel Network Calculus library
Full text linkThis paper describes Nancy, a Network Calculus (NC) library that allows users
to perform complex min-plus and max-plus algebra operations efficiently. To the
best of our knowledge, Nancy is the only open-source library that implements
operations working on arbitrary piecewise affine functions, as well as to
implement some of them (e.g. sub-additive closure and function composition).
Nancy allows researchers to compute NC results using a straightforward syntax,
which matches the algebraic one. Moreover, it is designed having computational
efficiency in mind: it exploits optimizations of data structures, it uses
inheritance to allow for faster algorithms when they are available (e.g., for
specific subclasses of functions), and it is natively parallel, thus reaping
the benefit of multicore hardware. This makes it usable to solve NC problems
which were previously considered beyond the realm of tractable
Computationally Efficient Worst-Case Analysis of Flow-Controlled Networks with Network Calculus
Full text linkNetworks with hop-by-hop flow control occur in several contexts, from data
centers to systems architectures (e.g., wormhole-routing networks on chip). A
worst-case end-to-end delay in such networks can be computed using Network
Calculus (NC), an algebraic theory where traffic and service guarantees are
represented as curves in a Cartesian plane. NC uses transformation operations,
e.g., the min-plus convolution, to model how the traffic profile changes with
the traversal of network nodes. NC allows one to model flow-controlled systems,
hence one can compute the end-to-end service curve describing the minimum
service guaranteed to a flow traversing a tandem of flow-controlled nodes.
However, while the algebraic expression of such an end-to-end service curve is
quite compact, its computation is often intractable from an algorithmic
standpoint: data structures tend to grow quickly to unfeasibly large sizes,
making operations intractable, even with as few as three hops. In this paper,
we propose computational and algebraic techniques to mitigate the above
problem. We show that existing techniques (such as reduction to compact
domains) cannot be used in this case, and propose an arsenal of solutions,
which include methods to mitigate the data representation space explosion as
well as computationally efficient algorithms for the min-plus convolution
operation. We show that our solutions allow a significant speedup, enable
analysis of previously unfeasible case studies, and -- since they do not rely
on any approximation -- still provide exact results.Comment: 27 pages, 33 figure
Extending the Network Calculus Algorithmic Toolbox for Ultimately Pseudo-Periodic Functions: Pseudo-Inverse and Composition
Full text linkNetwork Calculus (NC) is an algebraic theory that represents traffic and
service guarantees as curves in a Cartesian plane, in order to compute
performance guarantees for flows traversing a network. NC uses transformation
operations, e.g., min-plus convolution of two curves, to model how the traffic
profile changes with the traversal of network nodes. Such operations, while
mathematically well-defined, can quickly become unmanageable to compute using
simple pen and paper for any non-trivial case, hence the need for algorithmic
descriptions. Previous work identified the class of piecewise affine functions
which are ultimately pseudo-periodic (UPP) as being closed under the main NC
operations and able to be described finitely. Algorithms that embody NC
operations taking as operands UPP curves have been defined and proved correct,
thus enabling software implementations of these operations. However, recent
advancements in NC make use of operations, namely the lower pseudo-inverse,
upper pseudo-inverse, and composition, that are well defined from an algebraic
standpoint, but whose algorithmic aspects have not been addressed yet. In this
paper, we introduce algorithms for the above operations when operands are UPP
curves, thus extending the available algorithmic toolbox for NC. We discuss the
algorithmic properties of these operations, providing formal proofs of
correctness.Comment: Preprint submitted to Journal of Discrete Event Dynamic System
Isospeed: Improving (min,+) Convolution by Exploiting (min,+)/(max,+) Isomorphism (Artifact)
Full text link(min,+) convolution is the key operation in (min,+) algebra, a theory often used to compute performance bounds in real-time systems. As already observed in many works, its algorithm can be computationally expensive, due to the fact that: i) its complexity is superquadratic with respect to the size of the operands; ii) operands must be extended before starting its computation, and iii) said extension is tied to the least common multiple of the operand periods.
In this paper, we leverage the isomorphism between (min,+) and (max,+) algebras to devise a new algorithm for (min,+) convolution, in which the need for operand extension is minimized. This algorithm is considerably faster than the ones known so far, and it allows us to abate the computation times of (min,+) convolution by orders of magnitude
Isospeed: Improving (min,+) Convolution by Exploiting (min,+)/(max,+) Isomorphism
Full text link(min,+) convolution is the key operation in (min,+) algebra, a theory often used to compute performance bounds in real-time systems. As already observed in many works, its algorithm can be computationally expensive, due to the fact that: i) its complexity is superquadratic with respect to the size of the operands; ii) operands must be extended before starting its computation, and iii) said extension is tied to the least common multiple of the operand periods.
In this paper, we leverage the isomorphism between (min,+) and (max,+) algebras to devise a new algorithm for (min,+) convolution, in which the need for operand extension is minimized. This algorithm is considerably faster than the ones known so far, and it allows us to reduce the computation times of (min,+) convolution by orders of magnitude
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Study and implementation of a Network Calculus tool for worst case performance on Networks-on-Chip
No full textA Network on Chip is the communication system on an integrated circuit that enables the IP cores to exchange data with each other.
Inspired by large-scale network technologies, they are adapted to different requirements of integrated systems of area coverage, end-to-end delay and bandwidth.
With the diffusion mobile technologies and their increasing requirements of miniaturization and performance, it's increasingly difficult to design ad-hoc NoCs.
Network Calculus is a mathematical framework analysing performance guarantees in computer networks.
While successfully applied for the internet, its models are too simple to represent the NoC routing technologies, in particular wormhole routing, and its congestion issues.
To aid design of NoCs, in this work we show how to model wormhole networks using Network Calculus as a series of FCFS buffers, and how these models were used to develop an integrated tool to study worst-case end-to-end delay on a wormhole network
- …
