The Experts below are selected from a list of 26598 Experts worldwide ranked by ideXlab platform

Michitaka Kameyama - One of the best experts on this subject based on the ideXlab platform.

  • ISMVL - Switch Block Architecture for Multi-Context FPGAs Using Hybrid Multiple-Valued/Binary Context Switching Signals
    36th International Symposium on Multiple-Valued Logic (ISMVL'06), 2006
    Co-Authors: Y. Nakatani, Masanori Hariyama, Michitaka Kameyama
    Abstract:

    Multi-Context (MC) FPGAs have multiple memory bits per configuration bit forming configuration planes for fast Switching between Contexts. Large amount of memory causes significant overhead in area and power consumption. This paper presents two key technologies. The first is a floating-gate-MOS functional pass gate that merges storage and Switching functions area-efficiently. The second is the use of a hybrid multiple-valued/binary Context Switching signal that eliminates redundancy of a conventional MC-switch with high scalability. The transistor count of the proposed MC-switch is reduced to 7% in comparison with that of a SRAM-based one.

  • IPDPS - Architecture of a multi-Context FPGA using a hybrid multiple-valued/binary Context Switching signal
    Proceedings 20th IEEE International Parallel & Distributed Processing Symposium, 2006
    Co-Authors: Y. Nakatani, Masanori Hariyama, Michitaka Kameyama
    Abstract:

    Multi-Context FPGAs have multiple memory bits per configuration bit forming configuration planes for fast Switching between Contexts. Large amount of memory causes significant overhead in area and power consumption. This paper presents two key technologies. The first is a floating-gate-MOS functional pass gate that merges storage and Switching functions area - efficiently. The second is the use of a hybrid multiple-valued/binary Context Switching signal that eliminates redundancy of a conventional multi-Context (MC) switch with high scalability. The transistor count of the proposed MC-switch is reduced to 7% in comparison with that of a SRAM-based one.

Georg Zetzsche - One of the best experts on this subject based on the ideXlab platform.

  • The complexity of bounded Context Switching with dynamic thread creation.
    arXiv: Formal Languages and Automata Theory, 2020
    Co-Authors: Pascal Baumann, Rupak Majumdar, Ramanathan S. Thinniyam, Georg Zetzsche
    Abstract:

    Dynamic networks of concurrent pushdown systems (DCPS) are a theoretical model for multi-threaded recursive programs with shared global state and dynamical creation of threads. The (global) state reachability problem for DCPS is undecidable in general, but Atig et al. (2009) showed that it becomes decidable, and is in 2EXPSPACE, when each thread is restricted to a fixed number of Context switches. The best known lower bound for the problem is EXPSPACE-hard and this lower bound follows already when each thread is a finite-state machine and runs atomically to completion (i.e., does not switch Contexts). In this paper, we close the gap by showing that state reachability is 2EXPSPACE-hard already with only one Context switch. Interestingly, state reachability analysis is in EXPSPACE both for pushdown threads without Context switches as well as for finite-state threads with arbitrary Context switches. Thus, recursive threads together with a single Context switch provide an exponential advantage. Our proof techniques are of independent interest for 2EXPSPACE-hardness results. We introduce transducer-defined Petri nets, a succinct representation for Petri nets, and show coverability is 2EXPSPACE-hard for this model. To show 2EXPSPACE-hardness, we present a modified version of Lipton's simulation of counter machines by Petri nets, where the net programs can make explicit recursive procedure calls up to a bounded depth.

  • Bounded Context Switching for Valence Systems
    arXiv: Logic in Computer Science, 2018
    Co-Authors: Roland Meyer, Sebastian Muskalla, Georg Zetzsche
    Abstract:

    We study valence systems, finite-control programs over infinite-state memories modeled in terms of graph monoids. Our contribution is a notion of bounded Context Switching (BCS). Valence systems generalize pushdowns, concurrent pushdowns, and Petri nets. In these settings, our definition conservatively generalizes existing notions. The main finding is that reachability within a bounded number of Context switches is in NP, independent of the memory (the graph monoid). Our proof is genuinely algebraic, and therefore contributes a new way to think about BCS. In addition, we exhibit a class of storage mechanisms for which BCS reachability belongs to P.

  • bounded Context Switching for valence systems
    International Conference on Concurrency Theory, 2018
    Co-Authors: Roland Meyer, Sebastian Muskalla, Georg Zetzsche
    Abstract:

    We study valence systems, finite-control programs over infinite-state memories modeled in terms of graph monoids. Our contribution is a notion of bounded Context Switching (BCS). Valence systems generalize pushdowns, concurrent pushdowns, and Petri nets. In these settings, our definition conservatively generalizes existing notions. The main finding is that reachability within a bounded number of Context switches is in NPTIME, independent of the memory (the graph monoid). Our proof is genuinely algebraic, and therefore contributes a new way to think about BCS. In addition, we exhibit a class of storage mechanisms for which BCS reachability belongs to PTIME.

  • CONCUR - Bounded Context Switching for Valence Systems
    2018
    Co-Authors: Roland Meyer, Sebastian Muskalla, Georg Zetzsche
    Abstract:

    We study valence systems, finite-control programs over infinite-state memories modeled in terms of graph monoids. Our contribution is a notion of bounded Context Switching (BCS). Valence systems generalize pushdowns, concurrent pushdowns, and Petri nets. In these settings, our definition conservatively generalizes existing notions. The main finding is that reachability within a bounded number of Context switches is in NPTIME, independent of the memory (the graph monoid). Our proof is genuinely algebraic, and therefore contributes a new way to think about BCS. In addition, we exhibit a class of storage mechanisms for which BCS reachability belongs to PTIME.

Y. Nakatani - One of the best experts on this subject based on the ideXlab platform.

  • ISMVL - Switch Block Architecture for Multi-Context FPGAs Using Hybrid Multiple-Valued/Binary Context Switching Signals
    36th International Symposium on Multiple-Valued Logic (ISMVL'06), 2006
    Co-Authors: Y. Nakatani, Masanori Hariyama, Michitaka Kameyama
    Abstract:

    Multi-Context (MC) FPGAs have multiple memory bits per configuration bit forming configuration planes for fast Switching between Contexts. Large amount of memory causes significant overhead in area and power consumption. This paper presents two key technologies. The first is a floating-gate-MOS functional pass gate that merges storage and Switching functions area-efficiently. The second is the use of a hybrid multiple-valued/binary Context Switching signal that eliminates redundancy of a conventional MC-switch with high scalability. The transistor count of the proposed MC-switch is reduced to 7% in comparison with that of a SRAM-based one.

  • IPDPS - Architecture of a multi-Context FPGA using a hybrid multiple-valued/binary Context Switching signal
    Proceedings 20th IEEE International Parallel & Distributed Processing Symposium, 2006
    Co-Authors: Y. Nakatani, Masanori Hariyama, Michitaka Kameyama
    Abstract:

    Multi-Context FPGAs have multiple memory bits per configuration bit forming configuration planes for fast Switching between Contexts. Large amount of memory causes significant overhead in area and power consumption. This paper presents two key technologies. The first is a floating-gate-MOS functional pass gate that merges storage and Switching functions area - efficiently. The second is the use of a hybrid multiple-valued/binary Context Switching signal that eliminates redundancy of a conventional multi-Context (MC) switch with high scalability. The transistor count of the proposed MC-switch is reduced to 7% in comparison with that of a SRAM-based one.

Kiran Puttegowda - One of the best experts on this subject based on the ideXlab platform.

  • Context Switching in a Run-Time Reconfigurable System
    The Journal of Supercomputing, 2003
    Co-Authors: Kiran Puttegowda, David I. Lehn, Jae H. Park, Peter Athanas, Mark Jones
    Abstract:

    A distinguishing feature of reconfigurable computing over rapid prototyping is its ability to configure the computational fabric on-line while an application is running. Conventional reconfigurable computing platforms utilize commodity FPGAs, which typically have relatively long configuration times. Shrinking the configuration time down to the nanosecond region opens possibilities for rapid Context Switching and virtualizing the computational resources. An experimental Context-Switching FPGA, called the CSRC, has been created by BAE Systems, and gives researchers the opportunity to explore Context-Switching applications. This paper presents results obtained from constructing both control-driven and data-driven Context Switching applications on the CSRC device, along with unique properties of the run-time and compile-time environment.

  • Context Switching Strategies in a Run-Time Reconfigurable system
    2002
    Co-Authors: Kiran Puttegowda
    Abstract:

    A distinctive feature of run-time reconfigurable systems is the ability to change the configuration of programmable resources during execution. This opens a number of possibilities such as virtualisation of computational resources, simplified routing and in certain applications lower power. Seamless run-time reconfiguration requires rapid configuration. Commodity programmable devices have relatively long configuration time, which makes them poor candidates for run-time reconfigurable systems. Reducing this reconfiguration time to the order of nano seconds will enable rapid run-time reconfiguration. Having multiple configuration planes and Switching between them while processing data is one approach towards achieving rapid reconfiguration. An experimental Context Switching programmable device, called the Context Switching Reconfigurable Computer (CSRC), has been created by BAE Systems, which provided opportunities to explore Context-Switching strategies for run-time reconfigurable systems. The work presented here studies this approach for run-time reconfiguration, by applying the concepts to develop applications on a Context Switching reconfigurable system. The work also discusses the advantages and disadvantages of such an approach and ways of leveraging the concept for efficient computing. To my Parents and Sisters without whom nothing would have been possible.

  • Evaluation of Rapid Context Switching on a CSRC Device
    2002
    Co-Authors: David I. Lehn, Kiran Puttegowda, Jae H. Park, Peter Athanas
    Abstract:

    One property that distinguishes reconfigurable computing from rapid prototyping is the ability to configure the computational fabric on-line while an application is running. Conventional reconfigurable computing platforms utilize commodity FPGAs, which typically have relatively long configuration times. Shrinking the configuration time down to the nanosecond region opens possibilities for rapid Context Switching and virtualizing the computational resources. An experimental Context Switching FPGA, called the CSRC, has been created by BAE Systems, and gives researchers the opportunity to explore Context-Switching applications. This paper presents results obtained from constructing both control-driven and data-driven Context Switching applications on the CSRC device, along with unique properties of the run-time and compile-time environment.

Roland Meyer - One of the best experts on this subject based on the ideXlab platform.

  • Bounded Context Switching for Valence Systems
    arXiv: Logic in Computer Science, 2018
    Co-Authors: Roland Meyer, Sebastian Muskalla, Georg Zetzsche
    Abstract:

    We study valence systems, finite-control programs over infinite-state memories modeled in terms of graph monoids. Our contribution is a notion of bounded Context Switching (BCS). Valence systems generalize pushdowns, concurrent pushdowns, and Petri nets. In these settings, our definition conservatively generalizes existing notions. The main finding is that reachability within a bounded number of Context switches is in NP, independent of the memory (the graph monoid). Our proof is genuinely algebraic, and therefore contributes a new way to think about BCS. In addition, we exhibit a class of storage mechanisms for which BCS reachability belongs to P.

  • bounded Context Switching for valence systems
    International Conference on Concurrency Theory, 2018
    Co-Authors: Roland Meyer, Sebastian Muskalla, Georg Zetzsche
    Abstract:

    We study valence systems, finite-control programs over infinite-state memories modeled in terms of graph monoids. Our contribution is a notion of bounded Context Switching (BCS). Valence systems generalize pushdowns, concurrent pushdowns, and Petri nets. In these settings, our definition conservatively generalizes existing notions. The main finding is that reachability within a bounded number of Context switches is in NPTIME, independent of the memory (the graph monoid). Our proof is genuinely algebraic, and therefore contributes a new way to think about BCS. In addition, we exhibit a class of storage mechanisms for which BCS reachability belongs to PTIME.

  • CONCUR - Bounded Context Switching for Valence Systems
    2018
    Co-Authors: Roland Meyer, Sebastian Muskalla, Georg Zetzsche
    Abstract:

    We study valence systems, finite-control programs over infinite-state memories modeled in terms of graph monoids. Our contribution is a notion of bounded Context Switching (BCS). Valence systems generalize pushdowns, concurrent pushdowns, and Petri nets. In these settings, our definition conservatively generalizes existing notions. The main finding is that reachability within a bounded number of Context switches is in NPTIME, independent of the memory (the graph monoid). Our proof is genuinely algebraic, and therefore contributes a new way to think about BCS. In addition, we exhibit a class of storage mechanisms for which BCS reachability belongs to PTIME.

  • ESA - On the Complexity of Bounded Context Switching.
    2017
    Co-Authors: Peter Chini, Roland Meyer, Jonathan Kolberg, Andreas Krebs, Prakash Saivasan
    Abstract:

    Bounded Context Switching (BCS) is an under-approximate method for finding violations to safety properties in shared-memory concurrent programs. Technically, BCS is a reachability problem that is known to be NP-complete. Our contribution is a parameterized analysis of BCS. The first result is an algorithm that solves BCS when parameterized by the number of Context switches (cs) and the size of the memory (m) in O*(m^(cs)2^(cs)). This is achieved by creating instances of the easier problem Shuff which we solve via fast subset convolution. We also present a lower bound for BCS of the form m^o(cs / log(cs)), based on the exponential time hypothesis. Interestingly, the gap is closely related to a conjecture that has been open since FOCS'07. Further, we prove that BCS admits no polynomial kernel. Next, we introduce a measure, called scheduling dimension, that captures the complexity of schedules. We study BCS parameterized by the scheduling dimension (sdim) and show that it can be solved in O*((2m)^(4sdim)4^t), where t is the number of threads. We consider variants of the problem for which we obtain (matching) upper and lower bounds.

  • On the Complexity of Bounded Context Switching
    arXiv: Formal Languages and Automata Theory, 2016
    Co-Authors: Peter Chini, Roland Meyer, Jonathan Kolberg, Andreas Krebs, Prakash Saivasan
    Abstract:

    Bounded Context Switching (BCS) is an under-approximate method for finding violations to safety properties in shared memory concurrent programs. Technically, BCS is a reachability problem that is known to be NP-complete. Our contribution is a parameterized analysis of BCS. The first result is an algorithm that solves BCS when parameterized by the number of Context switches (cs) and the size of the memory (m) in O*(m^(cs)2^(cs)). This is achieved by creating instances of the easier problem Shuff which we solve via fast subset convolution. We also present a lower bound for BCS of the form m^o(cs / log(cs)), based on the exponential time hypothesis. Interestingly, closing the gap means settling a conjecture that has been open since FOCS'07. Further, we prove that BCS admits no polynomial kernel. Next, we introduce a measure, called scheduling dimension, that captures the complexity of schedules. We study BCS parameterized by the scheduling dimension (sdim) and show that it can be solved in O*((2m)^(4sdim)4^t)$, where t is the number of threads. We consider variants of the problem for which we obtain (matching) upper and lower bounds.