作者：
Fink, JiriHurink, Johann L.Univ Twente
Fac Elect Engn Math & Comp Sci POB 217 NL-7500 AE Enschede Netherlands Charles Univ Prague
Fac Math & Phys Dept Theoret Comp Sci & Math Log Malostranske Namesti 25 Prague 11800 Czech Republic
This paper studies a planning problem for heating water. Hereby, boilers (e.g. gas or electric boilers, heat pumps or microCHPs) are used to heat the water and store it for domestic demands. We consider a simple boile...
详细信息
This paper studies a planning problem for heating water. Hereby, boilers (e.g. gas or electric boilers, heat pumps or microCHPs) are used to heat the water and store it for domestic demands. We consider a simple boiler which is either turned on or turned off and has a buffer of limited capacity. The energy needed to run the boiler has to be bought on a day-ahead market, so we are interested in a planning which minimizes the cost to supply the boiler with energy. We present a greedy algorithm whose time complexity is O(T alpha(T)) where T is the number of time intervals and alpha is the inverse of Ackermann function. (C) 2021 Elsevier B.V. All rights reserved.
Graph algorithms on parallel architectures present an interesting case study for irregular applications. Among the graph algorithms popular in scientific computing, graph clustering or community detection has numerous...
详细信息
ISBN:
(纸本)9781450311212
Graph algorithms on parallel architectures present an interesting case study for irregular applications. Among the graph algorithms popular in scientific computing, graph clustering or community detection has numerous applications in computational biology. However, this operation also poses serious computational challenges because of irregular memory access patterns, large memory requirements, and their dependence on other auxiliary (also irregular) datastructures to supplement processing. In this paper, we address the problem of graph clustering on shared memory machines. We present a new OpenMP-based parallel algorithm called pClust-sm, which uses adjacency lists, hash tables and union-find data structures in parallel. The algorithm improves both the asymptotic runtime and memory complexities of a previous serial implementation. Preliminary results show that this algorithm can scale up to 8 threads (cores) of a shared memory machine on a real world metagenomics input graph with 1.2M vertices and 100M edges. More importantly, the new implementation drastically reduces the time to solution from the order of several hours to just over 4 minutes, and in addition, it enhances the problem size reach by at least one order of magnitude.
In this paper we present a design, suited to VLSI implementation, for a one-dimensional array to solve graph connectivity problems. The computational model is relatively primitive in that only the two end cells of the...
详细信息
In this paper we present a design, suited to VLSI implementation, for a one-dimensional array to solve graph connectivity problems. The computational model is relatively primitive in that only the two end cells of the array can interact with the external environment and only adjacent cells in the array are allowed to communicate. However, we show that an array of n + 1 cells can be used for a graph with n vertices to find the connected components, a spanning tree, or, when used in conjunction with a systolic priority queue, a minimum spanning tree. The area, time, and I/O requirements compare favorably with other models proposed for this problem in the case of sparse graphs.
暂无评论