ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Publication Date: 2019-07-13
    Description: Classical mesh partitioning algorithms were designed for rather static situations, and their straightforward application in a dynamical framework may lead to unsatisfactory results, e.g., excessive data migration among processors. Furthermore, special attention should be paid to their amenability to parallelization. In this paper, a novel parallel method for the dynamic partitioning of adaptive unstructured meshes is described. It is based on a linear representation of the mesh using self-avoiding walks.
    Keywords: Computer Systems
    Type: IPPS''99; 12-16 Apr. 1999; San Juan; Puerto Rico
    Format: application/pdf
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 2
    Publication Date: 2019-07-13
    Description: In this paper, we present a new approach to constructing a "self-avoiding" walk through a triangular mesh. Unlike the popular approach of visiting mesh elements using space-filling curves which is based on a geometric embedding, our approach is combinatorial in the sense that it uses the mesh connectivity only. We present an algorithm for constructing a self-avoiding walk which can be applied to any unstructured triangular mesh. The complexity of the algorithm is O(n x log(n)), where n is the number of triangles in the mesh. We show that for hierarchical adaptive meshes, the algorithm can be easily parallelized by taking advantage of the regularity of the refinement rules. The proposed approach should be very useful in the run-time partitioning and load balancing of adaptive unstructured grids.
    Keywords: Computer Programming and Software
    Type: 39th Symposium on Foundations of Computer Science; 8-11 Nov. 1998; Palo Alto, CA; United States
    Format: application/pdf
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 3
    Publication Date: 2019-07-13
    Description: Space-filling curves is a popular approach based on a geometric embedding for linearizing computational meshes. We present a new O(n log n) combinatorial algorithm for constructing a self avoiding walk through a two dimensional mesh containing n triangles. We show that for hierarchical adaptive meshes, the algorithm can be locally adapted and easily parallelized by taking advantage of the regularity of the refinement rules. The proposed approach should be very useful in the runtime partitioning and load balancing of adaptive unstructured grids.
    Keywords: Cybernetics, Artificial Intelligence and Robotics
    Type: SIAM Parallel Processing Conference; 22-24 Mar. 1999; San Antonio, TX; United States
    Format: application/pdf
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 4
    Publication Date: 2019-07-13
    Description: In this paper, we present a multi-threaded approach for the automatic load balancing of adaptive finite element (FE) meshes The platform of our choice is the EARTH multi-threaded system which offers sufficient capabilities to tackle this problem. We implement the adaption phase of FE applications oil triangular meshes and exploit the EARTH token mechanism to automatically balance the resulting irregular and highly nonuniform workload. We discuss the results of our experiments oil EARTH-SP2, on implementation of EARTH on the IBM SP2 with different load balancing strategies that are built into the runtime system.
    Keywords: Cybernetics, Artificial Intelligence and Robotics
    Type: 5th Symposium on Solving Irregularly Structured Problems in Parallel; 9-11 Aug. 1998; Berkeley, CA; United States
    Format: application/pdf
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 5
    Publication Date: 2019-07-18
    Description: In this paper, we present a multi-threaded approach for the automatic load balancing of adaptive finite element (FE) meshes. The platform of our choice is the EARTH multi-threaded system which offers sufficient capabilities to tackle this problem. We implement the question phase of FE applications on triangular meshes, and exploit the EARTH token mechanism to automatically balance the resulting irregular and highly nonuniform workload. We discuss the results of our experiments on EARTH-SP2, an implementation of EARTH on the IBM SP2, with different load balancing strategies that are built into the runtime system.
    Keywords: Numerical Analysis
    Type: 5th International Symposium on Solving Irregularly Structured Problems in Parallel; 9-11 Aug. 1998; Berkley, CA; United States
    Format: text
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 6
    ISSN: 1573-7640
    Keywords: Dataflow architecture ; loop scheduling ; storage allocation ; polynomial algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract In this paper, we consider the optimal loop scheduling and minimum storage allocation problems based on the argument-fetching dataflow architecture model. Under the argument-fetching model, the result generated by a node is stored in a unique location which is addressable by its successors. The main contribution of this paper includes: for loops containing no loop-carried dependences, we prove that the problem of allocating minimum storage required to support rate-optimal loop scheduling can be solved in polynomial time. The polynomial time algorithm is based on the fact that the constraint matrix in the formulation is totally unimodular. Since the instruction processing unit of an argument-fetching dataflow architecture is very much like a conventional processor architecture without a program counter, the solution of the optimal loop storage allocation problem for the former will also be useful for the latter.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 7
    ISSN: 1573-7640
    Keywords: Recurrence ; static data flow ; pipelining ; companion pipeline
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract This paper investigates the principles of mapping linear recurrences on static data flow computers. For a linear recurrence with a single variable, the key is to properly introduce a feedback loop in the machine level data flow graphs. We show that, in order to achieve maximum pipelining, thecritical dependence delay of the recurrence must be matched with the necessarycomputational delay of the graph. Two possible mapping techniques are discussed, which are (1) changing the dependence delay by introducing an additional companion pipeline; (2) changing the computational delay by inserting FIFOs. The mapping of the Valfor-iter construct, the major language feature for expressing recurrences in Val, is outlined.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 8
    ISSN: 1573-7640
    Keywords: MODULO SCHEDULING ; SOFTWARE PIPELINING ; REGISTERS ; ENUMERATION ; INSTRUCTION-LEVEL PARALLELISM
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Resource-constrained software-pipelining has played an increasingly significant role in exploiting instruction-level parallelism and has drawn intensive academic and industrial interest. The challenge is to find a schedule which is optimal : i.e., given the data dependence graph (DDG) for a loop, find the fastest possible schedule under given resource constraints while keeping register usage minimal. This paper proposes a novel enumeration based modulo scheduling approach to solve this problem. The proposed approach does not require any awkward reworking of constraints into linear form and employs a realistic register model. The set of schedules enumerated also allows us to characterize the schedule space and address questions such as whether schedules using a small number of registers tend to require a large number of function units. The proposed approach has been implemented under the MOST testbed at McGill University. Experimental results on more than 1000 loops from popular benchmark programs show that enumeration is generally faster at obtaining optimal schedules than integer linear programming approaches. Compared to Huff's Slack Scheduling , enumeration found a faster schedule for almost 15% of loops, with a mean improvement of 18%. 10% of the remaining loops required fewer registers under enumeration, with a mean reduction of 16%.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 9
    ISSN: 1573-7640
    Keywords: instruction-level parallelism ; software pipelining ; classical pipeline theory ; co-scheduling ; VLIW/superscalar architectures
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract Instruction scheduling methods which use the concepts developed by the classical pipeline theory have been proposed for architectures involving deeply pipelined function units. These methods rely on the construction of state diagrams (or automatons) to (i) efficiently represent the complex resource usage pattern; and (ii) analyze legal initiation sequences, i.e., those which do not cause a structural hazard. In this paper, we propose a state-diagram based approach for modulo scheduling or software pipelining, an instruction scheduling method for loops. Our approach adapts the classical pipeline theory for modulo scheduling, and, hence, the resulting theory is called Modulo-Scheduled pipeline (MS-pipeline) theory. The state diagram, called the Modulo-Scheduled (MS) state diagram is helpful in identifying legal initiation or latency sequences, that improve the number of instructions initiated in a pipeline. An efficient method, called Co-scheduling, which uses the legal initiation sequences as guidelines for constructing software pipelined schedules has been proposed in this paper. However, the complexity of the constructed MS-state diagram limits the usefulness of our Co-scheduling method. Further analysis of the MS-pipeline theory, reveals that the space complexity of the MS-state diagram can be significantly reduced by identifying primary paths. We develop the underlying theory to establish that the reduced MS-state diagram consisting only of primary paths is complete; i.e., it retains all the useful information represented by the original state diagram as far as scheduling of operations is concerned. Our experiments show that the number of paths in the reduced state diagram is significantly lower—by 1 to 3 orders of magnitude—compared to the number of paths in the original state diagram. The reduction in the state diagram facilitate the Co-scheduling method to consider multiple initiations sequences, and hence obtain more efficient schedules. We call the resulting method, enhanced Co-scheduling. The enhanced Co-scheduling method produced efficient schedules when tested on a set of 1153 benchmark loops. Further the schedules produced by this method are significantly better than those produced by Huff's Slack Scheduling method, a competitive software pipelining method, in terms of both the initiation interval of the schedules and the time taken to construct them.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 10
    ISSN: 1573-109X
    Source: Springer Online Journal Archives 1860-2000
    Topics: Electrical Engineering, Measurement and Control Technology
    Notes: Abstract In this paper we present a novel framework ofmulti-rate scheduling of signal processing programs represented by regular stream flow graphs (RSFGs). The main contribution of this paper is translating the scheduling problem of RSFGs into an equivalent problem in the domain of Karp-Miller computation graphs. A distinct feature of our scheduling framework—called themulti-rate software pipelining—is to allow maximum overlapping of operations from successive iterations, subject only to precedence constraints caused by data dependences. p ]We demonstrate that the scheduling of regular stream flow graphs can be formulated as a mathematical problem by capturing data dependences between two actors as a precedence relation between the firing of these actors. Using linear schedules, the problem is further translated into a linear program formulation. An efficient solution for the linear programming problem is obtained by first constructing what is called theprecedence graph. A polynomial-time solution is obtained by observing that the optimal computation rate is theminimum cost-to-time ratio cycle (MCTRC) in the precedence graph and using the well-established solution methods for the MCTRC problem. Finally, to minimize the buffer requirement for the obtained rate-optimal schedule, a graph coloring method based on thecyclic interval graph representation has been proposed.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...