@inproceedings{3262, author = {{Goltz, Ursula and Wehrheim, Heike}}, booktitle = {{Mathematical Foundations of Computer Science 1996, 21st International Symposium, MFCS'96, Cracow, Poland, September 2-6, 1996, Proceedings}}, editor = {{Penczek, Wojciech and Szalas, Andrzej}}, pages = {{394----406}}, title = {{{Causal Testing}}}, doi = {{10.1007/3-540-61550-4_165}}, year = {{1996}}, } @techreport{17418, author = {{Czumaj, Artur and Meyer auf der Heide, Friedhelm and Stemann, Volker}}, title = {{{Contention Resolution in Hashing Based Shared Memory Simulations}}}, year = {{1996}}, } @inproceedings{17419, abstract = {{We present a parallel algorithm for the rendering of complex three-dimensional scenes. The algorithm runs across heterogeneous architectures of PC-clusters consisting of a visualization-node, equipped with a powerful graphics adapter, and cluster nodes requiring weaker graphics capabilities only. The visualization-node renders a mixture of scene objects and simplified meshes (Reliefboards). The cluster nodes assist the visualization-node by asynchronous computing of Reliefboards, which are used to replace and render distant parts of the scene. Our algorithm is capable of gaining significant speedups if the cluster's nodes provide weak graphics adapters only. We trade the number of cluster nodes off the scene objects' image quality.}}, author = {{Grigoriev, Dima and Karpinski, Marek and Meyer auf der Heide, Friedhelm and Smolensky, Roman}}, booktitle = {{Proc. of 28th ACM-STOC}}, pages = {{612--621}}, publisher = {{Eurographics Symposium on Parallel Graphics and Visualization}}, title = {{{A lower bound for randomized algebraic decision trees}}}, volume = {{65453}}, year = {{1996}}, } @inproceedings{17483, abstract = {{In this paper we develop a model for communication time on parallel computers consisting of processors and a service network, i.e., a network performing services like broadcast, synchronization, and global variables. The implementation of the service network is done on a free configurable Transputer network. Our cost model describes the communication time of accesses to global variables and consists of a multi-linear function. The cost model includes the parameters packet size, send hot spot, and the number of processors accessing global variables. These parameters influence the communication time in a high degree and capture important parameters like contention. We implement a Bitonic Sort and a Connected Components algorithm (among others) and we show that our model is able to predict the communication time within a 10% error if indirect service networks are used. The applications show that it is easy for a programmer to determine the parameter values for our model and that our new cost model precisely predicts the communication time of parallel algorithms. Furthermore, we minimize the communication time of accesses to global variables by finding a balance between the number of messages in the network and their size. Our model predicts the optimal values for these parameters which we validate by experiments. A modified implementation of our routing which determines on-line the optimal parameter values for an access to a global variable achieves good speed ups.}}, author = {{Fischer, Matthias and Rethmann, Jochen and Wachsmann, Alf}}, booktitle = {{3rd Workshop on Abstract Machine Models for Parallel and Distributed Computing (AMW '96)}}, isbn = {{905199267X}}, pages = {{13–27}}, publisher = {{IOS Press}}, title = {{{A Realistic Cost Model for the Communication Time in Parallel Programs}}}, year = {{1996}}, } @inbook{17564, author = {{Bäumker, Armin and Dittrich, Wolfgang and Meyer auf der Heide, Friedhelm and Rieping, Ingo}}, booktitle = {{Lecture Notes in Computer Science}}, isbn = {{9783540616276}}, issn = {{0302-9743}}, pages = {{369--376}}, title = {{{Realistic parallel algorithms: Priority queue operations and selection for the BSP* Model}}}, doi = {{10.1007/bfb0024725}}, year = {{1996}}, } @inproceedings{1918, author = {{Dreier, Bernd and Huber, Annja and Zahn, Markus and Karl, Holger and Ungerer, Theo}}, booktitle = {{Proceedings Trends in Distributed Systems}}, title = {{{ReGTime - Rent Gigaflops someTimes}}}, year = {{1996}}, } @techreport{18352, abstract = {{In this report, we develop a cost model for the communication time on parallel computers consisting of processors and a service network, i.e., a network performing services like broadcast, synchronization, and global variables. Because we do not have a parallel computer at our disposal that is equipped with a service network, we emulate the service network on a reconfigurable Transputer network. Our cost model describes the communication time of accesses to global variables and consists of a multi­linear function. The cost model includes the parameters packet size, send hot spot (the number of messages sent out by one processor), and number of processors accessing global variables. We show that these parameters influence the communication time in a high degree and capture important parameters like network contention. We implement a Bitonic Sort, Sample Sort, Matrix Multiplication, and Connected Components algorithm, and we show that our model is able to predict the communication time within a 10% error if indirect service networks are used. The applications show that it is easy for a programer to determine the parameter values for our model and that our new cost model precisely predicts the communication time of parallel algorithms. We explore the interaction of hot spots and asynchrony and show that the influence of hot spots to the communication time is not as high as one would expect from theoretical considerations in a synchronous model. Therefore, we do not apprehend the hot spot in our cost model. Furthermore, we minimize the communication time of accesses to global variables by finding a balance between the number of messages in the network and their size. Our model predicts the optimal values for these parameters which we validate by experiments. A modified implementation of our routing which determines on­line the optimal parameter values for an access to a global variable achieves good speed ups. }}, author = {{Fischer, Matthias and Rethmann, Jochen and Wachsmann, Alf}}, title = {{{A Realistic Cost Model for the Communication Time in Parallel Programs on Parallel Computers Using a Service Hardware}}}, year = {{1996}}, } @phdthesis{2181, author = {{Scheideler, Christian}}, publisher = {{University of Paderborn, Germany}}, title = {{{Universal routing strategies}}}, year = {{1996}}, } @article{2182, author = {{Meyer auf der Heide, Friedhelm and Scheideler, Christian and Stemann, Volker}}, journal = {{Theor. Comput. Sci.}}, number = {{2}}, pages = {{245----281}}, title = {{{Exploiting Storage Redundancy to Speed up Randomized Shared Memory Simulations}}}, doi = {{10.1016/0304-3975(96)00032-1}}, year = {{1996}}, } @inproceedings{2183, author = {{Meyer auf der Heide, Friedhelm and Scheideler, Christian}}, booktitle = {{FOCS}}, pages = {{370----379}}, title = {{{Deterministic Routing with Bounded Buffers: Turning Offline into Online Protocols}}}, year = {{1996}}, } @inproceedings{2184, author = {{Meyer auf der Heide, Friedhelm and Scheideler, Christian}}, booktitle = {{SOFSEM}}, pages = {{16----33}}, publisher = {{Springer}}, title = {{{Communication in Parallel Systems}}}, volume = {{1175}}, year = {{1996}}, } @inproceedings{2186, author = {{Cypher, Robert and Meyer auf der Heide, Friedhelm and Scheideler, Christian and Vöcking, Berthold}}, booktitle = {{STOC}}, pages = {{356----365}}, publisher = {{ACM}}, title = {{{Universal Algorithms for Store-and-Forward and Wormhole Routing}}}, year = {{1996}}, } @proceedings{7796, editor = {{Engels, Gregor and Ehrig, Hartmut and Rozenberg, Grzegorz and Skowron, Andrzej}}, number = {{3-4}}, publisher = {{IOS Press}}, title = {{{Special Issue on Graph Transformations}}}, volume = {{26}}, year = {{1996}}, } @inproceedings{7834, abstract = {{The concept of views is used on two levels. First, so-called design views are developed for structuring specifications, that is, a system is modeled according to different views (e.g., representing the needs of different kinds of users) which have to be synchronized afterwards in order to build the whole system. Views can be specified by means of typed graph transformation systems, where the type graph determines the visible types and the productions describe the known operations of that view. The synchronization of views is done by the construction of cooperative parallel composition of graph transformation systems, developed by Leila Ribeiro and presented at the same seminar. If the specification is complete, a view may describe an observation of the system in operation. In this case we speak of a user view. It turns out that the semantics of such a view cannot be described by computations (i.e., graph transformations), but just by observations of computations of the global system. Such observations of computations cannot be represented by graph transformations in the usual sense because a local view may lack operations (productions) of the global system, so that state changes may be observed that do not have a cause in the local view. Therefore, the notion of graph transition is introduced as loose semantics for productions, where the production specifies only a lower bound to the activities that are to happen during application. Contrastingly, in the classical doublepushout approach to graph rewriting, productions are interpreted as complete descriptions of the transformations to be performed. For typed graph transformation systems a transition sequence semantics is developed, comprising all finite and infinite sequences of transitions in a system. Moreover, this semantics is shown to be compositional w.r.t. the synchronization of views.}}, author = {{Ehrig, Hartmut and Heckel, Reiko and Padberg, Julia and Taentzer, Gabriele and Wolter, Uwe and Corradini, Andrea and Engels, Gregor}}, booktitle = {{Report on the Dagstuhl-Seminar 9637 on Graph Transformations in Computer Science}}, number = {{155}}, pages = {{11--12}}, publisher = {{Technical University of Berlin}}, title = {{{Synchronization of Views and Loose Semantics of Typed Graph Productions}}}, year = {{1996}}, } @inproceedings{7835, author = {{Heckel, Reiko}}, booktitle = {{Report on the Dagstuhl-Seminar 9637 on Graph Transformations in Computer Science}}, number = {{155}}, pages = {{12--13}}, publisher = {{Technical University of Berlin}}, title = {{{Behavioral Constraints for Loose Graph Transformation Systems}}}, year = {{1996}}, } @inproceedings{7836, abstract = {{A large industrial process, software maintenance, has been modelled by using the process modelling language SOCCA. The paper reports about the experiences with this trial. In particular, feasibility, expressiveness, quality and the overall benefits of a formal SOCCA model are discussed and compared to the formerly existing informal process description. In order to illustrate the results, a well chosen process model fragment from the larger model is outlined in detail. It addresses in particular the human-intensive cooperation within the process and shows the seamless combination of technical components and human agent components in the SOCCA model. The main conclusions from this trial are that formal SOCCA models are suited to model realistic industrial processes and that due to an intrinsic modular structure of a SOCCA model, even huge models remain reasonably readable and understandable}}, author = {{de Bunje, Tineke and Engels, Gregor and Groenewegen, Luuk and Matsinger, Aart and Rijnbeek, Martin}}, booktitle = {{Proceedings of the Fourth International Conference on the Software Process (ICSP 1996), Brighton (UK)}}, pages = {{13--26}}, publisher = {{IEEE Computer Society}}, title = {{{Industrial maintenance modelled in SOCCA: an experience report}}}, doi = {{http://dx.doi.org/10.1109/ICSP.1996.565021}}, year = {{1996}}, } @inproceedings{7837, abstract = {{In order to manage the complexity of large system specifications, they have to be decomposed into subspecifications. Each subspecification describes a certain part of the system. This might be a certain aspect, like the data, dynamic, or functional aspect, as it is known from object-oriented modelling techniques. Or it might be a certain view onto the system, as it is known from database modelling techniques. The talk motivates the usage of views in graph grammarbased specifications. First, the usage of typed graph grammars inherently ensures an integration of the data and the functional aspect within a view. Second, it is explained that it is not appropriate in case of views to have a fixed semantics. The standard fixed semantics, i.e. a graph transformation system, has to be relaxed to a loose semantics, i.e. a graph transition system. This reflects the idea that a view models only a part of the complete system. Other views may overlap a view with respect to data or functionality. A complete system specification is yielded by exploiting the approach of cooperative parallel composition of graph grammars (see talk by Leila Ribeiro).}}, author = {{Engels, Gregor and Ehrig, Hartmut and Heckel, Reiko and Taentzer, Gabriele and Corradini, Andrea}}, booktitle = {{Report on Dagstuhl-Seminar 9637 on Graph Transformations in Computer Science}}, pages = {{11}}, publisher = {{Technical University of Berlin}}, title = {{{A View-Based Approach to System Modelling}}}, volume = {{155}}, year = {{1996}}, } @inproceedings{7838, abstract = {{Object-oriented specification mechanisms have become famous for modelling structure and behaviour together in terms of autonomous objects communicating via message passing. However, whereas most object-oriented specification methods are strong in modelling the local behaviour of single objects, they fall short on modelling the coordinated behaviour and collaboration of several objects together The aim of this paper is to contribute to fill this gap. The paper reports on concepts, language constructs, and experiences with three collaboration formalisms in the area of object-oriented specifications.}}, author = {{Engels, Gregor and Groenewegen, Luuk and Kappel, Gerti}}, booktitle = {{Proceedings of IFIP World Conference on IT Tools (1996), Canberra (Australia)}}, pages = {{437--452}}, publisher = {{Chapman & Hall}}, title = {{{Object-oriented specification of coordinated collaboration}}}, year = {{1996}}, } @techreport{8197, abstract = {{The framework of graph transformation combines the potentials and advantages of both, graphs and rules, into a single computational paradigm. In this paper we survey recent developments in applying graph transformation as a rule-based framework for the specification and development of systems, languages, and tools. After presenting the basic features of graph transformation, we discuss a spectrum of applications including the evaluation of functional expressions, the specification of an interactive graphical tool, an example specification for abstract data types, and the definition of a visual database query language. The case studies indicate the need for a graph transformation language that provides suitable structuring principles and is independent of a particular graph transformation approach. To this end, we sketch the basic features of the new graph- and rule-centered language Grace, currently under development, that permits systematic and structured specification and programming based on graph transformation.}}, author = {{Andries, Marc and Engels, Gregor and Habel, Annegret and Hoffmann, Berthold and Kreowski, Hans-Jörg and Kuske, Sabine and Plump, Detlef and Schürr, Andy and Taentzer, Gabriele}}, publisher = {{University of Bremen, Department of Mathematics and Computer Science}}, title = {{{Graph Transformation for Specification and Programming}}}, year = {{1996}}, } @techreport{8198, author = {{Busatto, Giorgio and Engels, Gregor}}, publisher = {{Vakgroep Informatica, Rijksuniversiteit Leiden}}, title = {{{Definition of an Encapsulated Hierarchical Graph Data Model: Static Aspects, Part 1.}}}, year = {{1996}}, }