4 Search Results for "Briskorn, Dirk"

Document
DOI: 10.4230/OASIcs.NG-RES.2026.3
Integrated Memory Grouping and Power-Aware MBIST Scheduling for MPSoCs

Authors: Koki Asahina and Yasuhiko Nakashima

Published in: OASIcs, Volume 140, 7th Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2026)

Abstract
Memory Built-In Self-Test (MBIST) is a widely adopted technique for testing memory. In modern large-scale SoCs, hundreds to thousands of embedded memories are integrated, and to test them efficiently, methods that group memories and test them in parallel within each group are employed. However, many existing approaches either do not account for test scheduling or rely on evolutionary methods, such as genetic algorithms (GAs), for grouping, which incur high computational costs. In this work, we propose a framework that covers the flow from memory grouping to test scheduling. Taking the specifications and layout information of multiple SRAMs into account, the framework comprises a flexible, fast memory grouping method and a scheduling method that minimizes the total test time under a power-constrained constraint. In the proposed approach, DBSCAN and rectangular partitioning are used to perform fast grouping while suppressing long routing connections, and an LPT-based greedy heuristic is employed to shorten the total test time under constraints on the power limit and the number of simultaneously active BIST controllers. Experimental evaluation using SRAM placement data based on the ASAP7 PDK shows that, compared with existing K-means, Greedy, and GA-based methods, the proposed method reduces the number of groups by up to 48% while achieving approximately 87× speedup in clustering runtime. Furthermore, compared with a commercial Industrial Solution, it reduces the test time by 53%. These results demonstrate that the proposed method provides high scalability and practical effectiveness for MBIST design, even in large-scale MPSoCs with a large number and variety of embedded memories.
Cite as

Koki Asahina and Yasuhiko Nakashima. Integrated Memory Grouping and Power-Aware MBIST Scheduling for MPSoCs. In 7th Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2026). Open Access Series in Informatics (OASIcs), Volume 140, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{asahina_et_al:OASIcs.NG-RES.2026.3,
  author =	{Asahina, Koki and Nakashima, Yasuhiko},
  title =	{{Integrated Memory Grouping and Power-Aware MBIST Scheduling for MPSoCs}},
  booktitle =	{7th Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2026)},
  pages =	{3:1--3:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-415-4},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{140},
  editor =	{Ali, Hazem Ismail and Kurunathan, Harrison},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2026.3},
  URN =		{urn:nbn:de:0030-drops-254214},
  doi =		{10.4230/OASIcs.NG-RES.2026.3},
  annote =	{Keywords: MBIST, DfT, Memory Grouping, Power-Aware Scheduling}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.37
Multi-League Sports Scheduling with Team Interdependencies: An Optimization Model

Authors: Nils Weidmann

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
Every year, a large number of matches must be scheduled for professional and amateur sports teams. Several constraints have to be considered, including the overall capacity of venues and interdependencies between teams of the same club. As interdependent teams of a club play in different leagues, finding an optimal solution is very challenging for practitioners. While the problem of respecting capacity restrictions is well-addressed in prior work, interdependencies between teams are widely neglected, despite being a problem of major importance in practice. This paper enhances the formal definition of the multi-league-sports scheduling problem to take team interdependencies into account. We create an optimization problem to be solved by means of integer linear programming, and prove the corresponding decision problem to be NP-complete by a polynomial reduction from 3-SAT. An implementation which was used to schedule German table tennis leagues of a certain district demonstrates the practical applicability of the approach.
Cite as

Nils Weidmann. Multi-League Sports Scheduling with Team Interdependencies: An Optimization Model. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{weidmann:LIPIcs.CP.2025.37,
  author =	{Weidmann, Nils},
  title =	{{Multi-League Sports Scheduling with Team Interdependencies: An Optimization Model}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{37:1--37:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.37},
  URN =		{urn:nbn:de:0030-drops-238986},
  doi =		{10.4230/LIPIcs.CP.2025.37},
  annote =	{Keywords: sports scheduling, linear optimization, constraint programming}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.5
Transition Dominance in Domain-Independent Dynamic Programming

Authors: J. Christopher Beck, Ryo Kuroiwa, Jimmy H. M. Lee, Peter J. Stuckey, and Allen Z. Zhong

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
Domain-independent dynamic programming (DIDP) is a model-based paradigm for dynamic programming (DP) that enables users to define DP models based on a state transition system. Heuristic search-based solvers have demonstrated strong performance in solving combinatorial optimization problems. In this paper, we formally define transition dominance in DIDP, where one transition consistently leads to better solutions than another, allowing the search process to safely ignore dominated transitions. To facilitate the efficient use of transition dominance, we introduce an interface for defining transition dominance and propose the use of state functions to cache values, thereby avoiding redundant computations when verifying transition dominance. Experimental results on DP models across multiple problem classes indicate that incorporating transition dominance and state functions yields a 5 to 10 times speed-up on average for different search algorithms within the DIDP framework compared to the baseline.
Cite as

J. Christopher Beck, Ryo Kuroiwa, Jimmy H. M. Lee, Peter J. Stuckey, and Allen Z. Zhong. Transition Dominance in Domain-Independent Dynamic Programming. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beck_et_al:LIPIcs.CP.2025.5,
  author =	{Beck, J. Christopher and Kuroiwa, Ryo and Lee, Jimmy H. M. and Stuckey, Peter J. and Zhong, Allen Z.},
  title =	{{Transition Dominance in Domain-Independent Dynamic Programming}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{5:1--5:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.5},
  URN =		{urn:nbn:de:0030-drops-238661},
  doi =		{10.4230/LIPIcs.CP.2025.5},
  annote =	{Keywords: Dominance, Dynamic Programming, Combinatorial Optimization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2014.92
Mathematical programming models for scheduling locks in sequence

Authors: Ward Passchyn, Dirk Briskorn, and Frits C.R. Spieksma

Published in: OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

Abstract
We investigate the scheduling of series of consecutive locks. This setting occurs naturally along canals and waterways. We describe a problem that generalizes different models that have been studied in literature. Our contribution is to (i) provide two distinct mathematical programming formulations, and compare them empirically, (ii) show how these models allow for minimizing emission by having the speed of a ship as a decision variable, (iii) to compare, on realistic instances, the optimum solution found by solving the models with the outcome of a decentralized heuristic.
Cite as

Ward Passchyn, Dirk Briskorn, and Frits C.R. Spieksma. Mathematical programming models for scheduling locks in sequence. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 92-106, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{passchyn_et_al:OASIcs.ATMOS.2014.92,
  author =	{Passchyn, Ward and Briskorn, Dirk and Spieksma, Frits C.R.},
  title =	{{Mathematical programming models for scheduling locks in sequence}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{92--106},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Funke, Stefan and Mihal\'{a}k, Mat\'{u}s},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.92},
  URN =		{urn:nbn:de:0030-drops-47553},
  doi =		{10.4230/OASIcs.ATMOS.2014.92},
  annote =	{Keywords: Mixed Integer Programming, Inland Waterways, Lock Scheduling}
}
  • Refine by Type
  • 4 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2025
  • 1 2014

  • Refine by Author
  • 1 Asahina, Koki
  • 1 Beck, J. Christopher
  • 1 Briskorn, Dirk
  • 1 Kuroiwa, Ryo
  • 1 Lee, Jimmy H. M.
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 2 OASIcs

  • Refine by Classification
  • 2 Mathematics of computing → Combinatorial optimization
  • 1 Hardware → Testing with distributed and parallel systems
  • 1 Theory of computation → Constraint and logic programming

  • Refine by Keyword
  • 1 Combinatorial Optimization
  • 1 DfT
  • 1 Dominance
  • 1 Dynamic Programming
  • 1 Inland Waterways
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact