The Experts below are selected from a list of 288 Experts worldwide ranked by ideXlab platform
Timothy Mark Pinkston - One of the best experts on this subject based on the ideXlab platform.
-
Worm-bubble flow control
Proceedings - International Symposium on High-Performance Computer Architecture, 2013Co-Authors: Lizhong Chen, Timothy Mark PinkstonAbstract:Deadlock-free flow control should be designed with minimal cost, particularly for on-chip designs where area and power resources are greatly constrained. While Bubble Flow Control, proposed a decade ago, can Avoid Deadlock in VCT-switched tori with only one virtual channel (VC), there has been no working solution for wormhole switching that achieves the similar objective. Wormhole switching allows the channel buffer size to be smaller than the packet size, thus is preferred by on-chip networks. However, wormhole packets can span multiple routers, thereby creating additional channel dependences and adding complexities in both Deadlock and starvation Avoidance. In this paper, we propose Worm-Bubble Flow Control (WBFC), a new flow control scheme that can Avoid Deadlock in wormhole-switched tori using minimally 1-flit-sized buffers per VC and one VC in total. Moreover, any wormhole-switched topology with embedded rings can use WBFC to Avoid Deadlock within each ring. Simulation results from synthetic traffic and PARSEC benchmarks show that the proposed approach can achieve significant throughput improvement and also area and energy savings compared to an optimized Dateline routing approach.
-
HPCA - Worm-Bubble Flow Control
2013 IEEE 19th International Symposium on High Performance Computer Architecture (HPCA), 2013Co-Authors: Lizhong Chen, Timothy Mark PinkstonAbstract:Deadlock-free flow control should be designed with minimal cost, particularly for on-chip designs where area and power resources are greatly constrained. While Bubble Flow Control, proposed a decade ago, can Avoid Deadlock in VCT-switched tori with only one virtual channel (VC), there has been no working solution for wormhole switching that achieves the similar objective. Wormhole switching allows the channel buffer size to be smaller than the packet size, thus is preferred by on-chip networks. However, wormhole packets can span multiple routers, thereby creating additional channel dependences and adding complexities in both Deadlock and starvation Avoidance. In this paper, we propose Worm-Bubble Flow Control (WBFC), a new flow control scheme that can Avoid Deadlock in wormhole-switched tori using minimally 1-flit-sized buffers per VC and one VC in total. Moreover, any wormhole-switched topology with embedded rings can use WBFC to Avoid Deadlock within each ring. Simulation results from synthetic traffic and PARSEC benchmarks show that the proposed approach can achieve significant throughput improvement and also area and energy savings compared to an optimized Dateline routing approach.
Maria Pia Fanti - One of the best experts on this subject based on the ideXlab platform.
-
CoDIT - A software tool for the decentralized control of AGV systems
2016 International Conference on Control Decision and Information Technologies (CoDIT), 2016Co-Authors: Maria Pia Fanti, Agostino Marcello Mangini, Giovanni Pedroncelli, Walter UkovichAbstract:This paper presents a software tool for the simulation of a decentralized control strategy to assign tasks to Autonomous Guided Vehicles (AGV) and coordinate their paths to Avoid Deadlock and collisions. We consider a zone-controlled guidepath network where a set of intelligent vehicles (agents) has to autonomously reach a consensus about the distribution of a set of tasks, i.e., a set of zones to be reached. To this aim, first the agents apply a discrete consensus algorithm in order to locally minimize the global cost for reaching the destination zone, then they move according to a decentralized coordination protocol that is based on a zone-controlled approach with the aim of Avoiding Deadlock and collisions. The software tool allows the user to define the guidepath network, then randomly generates the positions of AGVs and destinations and runs the two algorithms visually showing their behavior.
-
decentralized Deadlock free control for agv systems
Advances in Computing and Communications, 2015Co-Authors: Maria Pia Fanti, Agostino Marcello Mangini, Giovanni Pedroncelli, Walter UkovichAbstract:This paper proposes a decentralized control strategy to assign tasks to Autonomous Guided Vehicles (AGV) and coordinate their paths to Avoid Deadlock and collisions. We consider a zone-controlled guidepath network where a set of intelligent vehicles (agents) has to autonomously reach a consensus about the distribution of a set of tasks, i.e., a set of zones to be reached. To this aim the agents apply a discrete consensus algorithm in order to locally minimize the global cost for reaching the destination zone. Moreover, we present a decentralized coordination protocol that is based on a zone-controlled approach with the aim of Avoiding Deadlock and collisions.
-
ACC - Decentralized Deadlock-free control for AGV systems
2015 American Control Conference (ACC), 2015Co-Authors: Maria Pia Fanti, Agostino Marcello Mangini, Giovanni Pedroncelli, Walter UkovichAbstract:This paper proposes a decentralized control strategy to assign tasks to Autonomous Guided Vehicles (AGV) and coordinate their paths to Avoid Deadlock and collisions. We consider a zone-controlled guidepath network where a set of intelligent vehicles (agents) has to autonomously reach a consensus about the distribution of a set of tasks, i.e., a set of zones to be reached. To this aim the agents apply a discrete consensus algorithm in order to locally minimize the global cost for reaching the destination zone. Moreover, we present a decentralized coordination protocol that is based on a zone-controlled approach with the aim of Avoiding Deadlock and collisions.
-
Deadlock resolution strategy for automated manufacturing systems including conjunctive resource service
IEEE Transactions on Systems Man and Cybernetics - Part A: Systems and Humans, 2004Co-Authors: Maria Pia FantiAbstract:Automated manufacturing systems (AMSs) can process different parts according to operation sequences sharing a finite number of resources. In these systems, Deadlock situations can occur so that the flow of parts is permanently inhibited, and the processing of jobs is partially or completely blocked. Hence, one of the tasks of the control system is ruling resource allocation to prevent such situations from occurring. A large part of the existing literature focused on systems in which every operation is performed by only one resource. This paper proposes a Deadlock strategy to Avoid Deadlock conditions in more complex systems where multiple resource acquisitions are allowed to complete a working operation conjunctive resource service system (CRSS). The AMS structure and dynamics is described by a colored timed Petri net model, suitable for following resource changes and working procedure updating. Moreover, digraphs characterize the complex interactions between resources and jobs so that the conditions for the Deadlock occurrence are derived. Finally, an event-based controller is defined to Avoid Deadlock in CRSSs on the basis of the system state knowledge and of the given priority law ruling the concurrent job selection.
-
a Deadlock Avoidance strategy for agv systems modelled by coloured petri nets
International Workshop on Discrete Event Systems, 2002Co-Authors: Maria Pia FantiAbstract:Automated Guided Vehicle Systems (AGVSs) are material handling devices representing an efficient and flexible alternative for material handling. The vehicles follow a guidepath under computer control that assigns route, tasks, velocity, etc. However, the design of AGVSs has to take into account some management problems such as collisions and Deadlock. This paper presents a control strategy to Avoid Deadlock and collisions in zone controlled AGVSs. In particular, the control scheme manages the assignments of new paths and next zone acquisition. Moreover, we propose coloured timed Petri nets to model the AGVS structure and dynamics. The model allows us an easy implementation of the control strategy working on the basis of the knowledge of the system state.
Lizhong Chen - One of the best experts on this subject based on the ideXlab platform.
-
Worm-bubble flow control
Proceedings - International Symposium on High-Performance Computer Architecture, 2013Co-Authors: Lizhong Chen, Timothy Mark PinkstonAbstract:Deadlock-free flow control should be designed with minimal cost, particularly for on-chip designs where area and power resources are greatly constrained. While Bubble Flow Control, proposed a decade ago, can Avoid Deadlock in VCT-switched tori with only one virtual channel (VC), there has been no working solution for wormhole switching that achieves the similar objective. Wormhole switching allows the channel buffer size to be smaller than the packet size, thus is preferred by on-chip networks. However, wormhole packets can span multiple routers, thereby creating additional channel dependences and adding complexities in both Deadlock and starvation Avoidance. In this paper, we propose Worm-Bubble Flow Control (WBFC), a new flow control scheme that can Avoid Deadlock in wormhole-switched tori using minimally 1-flit-sized buffers per VC and one VC in total. Moreover, any wormhole-switched topology with embedded rings can use WBFC to Avoid Deadlock within each ring. Simulation results from synthetic traffic and PARSEC benchmarks show that the proposed approach can achieve significant throughput improvement and also area and energy savings compared to an optimized Dateline routing approach.
-
HPCA - Worm-Bubble Flow Control
2013 IEEE 19th International Symposium on High Performance Computer Architecture (HPCA), 2013Co-Authors: Lizhong Chen, Timothy Mark PinkstonAbstract:Deadlock-free flow control should be designed with minimal cost, particularly for on-chip designs where area and power resources are greatly constrained. While Bubble Flow Control, proposed a decade ago, can Avoid Deadlock in VCT-switched tori with only one virtual channel (VC), there has been no working solution for wormhole switching that achieves the similar objective. Wormhole switching allows the channel buffer size to be smaller than the packet size, thus is preferred by on-chip networks. However, wormhole packets can span multiple routers, thereby creating additional channel dependences and adding complexities in both Deadlock and starvation Avoidance. In this paper, we propose Worm-Bubble Flow Control (WBFC), a new flow control scheme that can Avoid Deadlock in wormhole-switched tori using minimally 1-flit-sized buffers per VC and one VC in total. Moreover, any wormhole-switched topology with embedded rings can use WBFC to Avoid Deadlock within each ring. Simulation results from synthetic traffic and PARSEC benchmarks show that the proposed approach can achieve significant throughput improvement and also area and energy savings compared to an optimized Dateline routing approach.
Roger D Chamberlain - One of the best experts on this subject based on the ideXlab platform.
-
efficient Deadlock Avoidance for streaming computation with filtering
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2012Co-Authors: Jeremy Buhler, Kunal Agrawal, Roger D ChamberlainAbstract:Parallel streaming computations have been studied extensively, and many languages, libraries, and systems have been designed to support this model of computation. In particular, we consider acyclic streaming computations in which individual nodes can choose to filter, or discard, some of their inputs in a data-dependent manner. In these applications, if the channels between nodes have finite buffers, the computation can Deadlock. One method of Deadlock Avoidance is to augment the data streams between nodes with occasional dummy messages; however, for general DAG topologies, no polynomial time algorithm is known to compute the intervals at which dummy messages must be sent to Avoid Deadlock. In this paper, we show that Deadlock Avoidance for streaming computations with filtering can be performed efficiently for a large class of DAG topologies. We first present a new method where each dummy message is tagged with a destination, so as to reduce the number of dummy messages sent over the network. We then give efficient algorithms for dummy interval computation in series-parallel DAGs. We finally generalize our results to a larger graph family, which we call the CS4 DAGs, in which every undirected Cycle is Single-Source and Single-Sink (CS4). Our results show that, for a large set of application topologies that are both intuitively useful and formalizable, the streaming model with filtering can be implemented safely with reasonable overhead.
-
PPOPP - Efficient Deadlock Avoidance for streaming computation with filtering
Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming - PPoPP '12, 2012Co-Authors: Jeremy Buhler, Kunal Agrawal, Roger D ChamberlainAbstract:Parallel streaming computations have been studied extensively, and many languages, libraries, and systems have been designed to support this model of computation. In particular, we consider acyclic streaming computations in which individual nodes can choose to filter, or discard, some of their inputs in a data-dependent manner. In these applications, if the channels between nodes have finite buffers, the computation can Deadlock. One method of Deadlock Avoidance is to augment the data streams between nodes with occasional dummy messages; however, for general DAG topologies, no polynomial time algorithm is known to compute the intervals at which dummy messages must be sent to Avoid Deadlock. In this paper, we show that Deadlock Avoidance for streaming computations with filtering can be performed efficiently for a large class of DAG topologies. We first present a new method where each dummy message is tagged with a destination, so as to reduce the number of dummy messages sent over the network. We then give efficient algorithms for dummy interval computation in series-parallel DAGs. We finally generalize our results to a larger graph family, which we call the CS4 DAGs, in which every undirected Cycle is Single-Source and Single-Sink (CS4). Our results show that, for a large set of application topologies that are both intuitively useful and formalizable, the streaming model with filtering can be implemented safely with reasonable overhead.
-
Deadlock Avoidance for streaming computations with filtering
ACM Symposium on Parallel Algorithms and Architectures, 2010Co-Authors: Kunal Agrawal, Jeremy Buhler, Roger D ChamberlainAbstract:The paradigm of computation on streaming data has received considerable recent attention. Streaming computations can be efficiently parallelized using systems of computing nodes organized in dataflow-like architectures. However, when these nodes have the ability to filter, or discard, some of their inputs, a system with finite buffering is vulnerable to Deadlock. In this paper, we formalize a model of streaming computation systems with filtering describe precisely the conditions under which such systems may Deadlock, and propose provably correct mechanisms to Avoid Deadlock. Our approach relies on adding extra "dummy" tokens to the data streams and does not require global run-time coordination among nodes or dynamic resizing of buffers. This approach is particularly well-suited to preventing Deadlock in distributed systems of diverse computing architectures, where global coordination or modification of buffer sizes may be difficult or impossible in practice.
Altug Iftar - One of the best experts on this subject based on the ideXlab platform.
-
Supervisory controller design for timed-place Petri nets.
Kybernetika, 2012Co-Authors: Aydın Aybar, Altug IftarAbstract:Supervisory controller design to Avoid Deadlock in discrete-event systems modeled by timed-place Petri nets (TPPNs) is considered. The recently introduced approach of place-stretching is utilized for this purpose. In this approach, given an original TPPN (OPN), a new TPPN, called the place-stretched Petri net (PSPN), is obtained. The PSPN has the property that its marking vector is sufficient to represent its state. By using this property, a supervisory controller design approach for TPPNs to Avoid Deadlock is proposed in the present work. An algorithm to determine the set of all the states of the PSPN which lead to Deadlock is presented. Using this set, a controller for the PSPN is defined. Using this controller, a controller for the OPN is then obtained. Assuming that the given Petri net is bounded, the proposed approach always finds a controller in finite time whenever there exists one. Furthermore, this controller, when exists, is maximally permissive.
-
Deadlock Avoidance controller design for timed petri nets using stretching
IEEE Systems Journal, 2008Co-Authors: Aydın Aybar, Altug IftarAbstract:The recently introduced method, which was called ldquostretching,rdquo is extended to timed Petri nets which may have both controllable and uncontrollable transitions. Using this method, a new Petri net, called ldquostretched Petri net,rdquo which has only unit firing durations, is obtained to represent a timed-transition Petri net. Using this net, the state of the original timed Petri net can be represented easily. This representation also makes it easy to design a supervisory controller for a timed Petri net for any purpose. In this paper, supervisory controller design to Avoid Deadlock is considered in particular. Using this method, a controller is first designed for the stretched Petri net. Then, using this controller, a controller for the original timed Petri net is obtained. Algorithms to construct the reachability sets of the stretched and original timed Petri nets, as well as algorithms to obtain the controller for the original timed Petri net are presented. These algorithms are implemented using Matlab. Examples are also presented to illustrate the introduced approach.
-
supervisory controller design for timed petri nets
International Conference on System of Systems Engineering, 2006Co-Authors: Aydın Aybar, Altug IftarAbstract:A method, called "stretching", is introduced to represent timed Petri nets. Using this method, a new Petri net, called "stretched Petri net", which has only unit delays, is obtained to represent a timed-transition Petri net. Using this net, the state of the original timed Petri net can be represented easily. This representation also makes it easy to design a supervisory controller for a timed Petri net for any purpose. In this paper, supervisory controller design to Avoid Deadlock is considered in particular. Using this method, a controller is first designed for the stretched Petri net. Then, using this controller, a controller for the original timed Petri net is obtained. Algorithms to construct the reachability sets of the stretched and original timed Petri nets, as well as algorithms to obtain the controller for the original timed Petri net are presented. These algorithms are implemented using MATLAB. An example is also presented to illustrate the introduced approach.
-
Decentralized supervisory controller design to Avoid Deadlock in Petri nets
International Journal of Control, 2003Co-Authors: Aydın Aybar, Altug IftarAbstract:A decentralized supervisory controller design approach, using overlapping decompositions, is proposed for discrete-event systems modelled by Petri nets to Avoid Deadlock. In this approach, the given original Petri net is first decomposed into overlapping Petri subnets. A controller for each disjoint Petri subnet is then designed. A controller for the expanded Petri net is next obtained by combining these controllers in a certain way. In the final phase, the controller obtained for the expanded Petri net is contracted in a certain way to obtain a controller for the original Petri net. It is proved that this final controller Avoids Deadlock in the original Petri net.
-
SoSE - Supervisory controller design for timed Petri nets
2006 IEEE SMC International Conference on System of Systems Engineering, 1Co-Authors: Aydın Aybar, Altug IftarAbstract:A method, called "stretching", is introduced to represent timed Petri nets. Using this method, a new Petri net, called "stretched Petri net", which has only unit delays, is obtained to represent a timed-transition Petri net. Using this net, the state of the original timed Petri net can be represented easily. This representation also makes it easy to design a supervisory controller for a timed Petri net for any purpose. In this paper, supervisory controller design to Avoid Deadlock is considered in particular. Using this method, a controller is first designed for the stretched Petri net. Then, using this controller, a controller for the original timed Petri net is obtained. Algorithms to construct the reachability sets of the stretched and original timed Petri nets, as well as algorithms to obtain the controller for the original timed Petri net are presented. These algorithms are implemented using MATLAB. An example is also presented to illustrate the introduced approach.
