Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-24T02:44:48.554Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal Scheduling for Exposed Datapath Architectures with Buffered Processing Units by ASP

Published online by Cambridge University Press:  10 August 2018

MARC DAHLEM Open the ORCID record for MARC DAHLEM [Opens in a new window] ,
ANOOP BHAGYANATH  and
KLAUS SCHNEIDER
MARC DAHLEM
Affiliation:
Insiders Technologies GmbH, Kaiserslautern, Germanyhttps://insiders-technologies.de
ANOOP BHAGYANATH
Affiliation:
Department of Computer Science, University of Kaiserslautern, Germanyhttps://es.cs.uni-kl.de
KLAUS SCHNEIDER
Affiliation:
Department of Computer Science, University of Kaiserslautern, Germanyhttps://es.cs.uni-kl.de
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Conventional processor architectures are restricted in exploiting instruction level parallelism (ILP) due to the relatively low number of programmer-visible registers. Therefore, more recent processor architectures expose their datapaths so that the compiler (1) can schedule parallel instructions to different processing units and (2) can make effective use of local storage of the processing units. Among these architectures, the Synchronous Control Asynchronous Dataflow (SCAD) architecture is a new exposed datapath architecture whose processing units are equipped with first-in first-out (FIFO) buffers at their input and output ports.

In contrast to register-based machines, the optimal code generation for SCAD is still a matter of research. In particular, SAT and SMT solvers were used to generate optimal resource constrained and optimal time constrained schedules for SCAD, respectively. As Answer Set Programming (ASP) offers better flexibility in handling such scheduling problems, we focus in this paper on using an answer set solver for both resource and time constrained optimal SCAD code generation. As a major benefit of using ASP, we are able to generate all optimal schedules for a given program which allows one to study their properties. Furthermore, the experimental results of this paper demonstrate that the answer set solver can compete with SAT solvers and outperforms SMT solvers. This paper is under consideration for acceptance in TPLP.

Keywords

Answer Set ProgrammingExposed Datapath ArchitecturesOptimal SchedulingCode Generation
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 18 , Special Issue 3-4: 34th International Conference on Logic Programming , July 2018 , pp. 438 - 451
Copyright
Copyright © Cambridge University Press 2018 

References

Aletà, A., Codina, J., González, A., and Kaeli, D. 2007. Heterogeneous clustered VLIW microarchitectures. In Code Generation and Optimization (CGO), San Jose, California, USA, pp. 354–366. IEEE Computer Society.Google Scholar
Andres, B., Gebser, M., Schaub, T., Haubelt, C., Reimann, F. and Glass, M. 2013. Symbolic system synthesis using answer set programming. In Cabalar, P. and Son, T. (Eds.), Logic Programming and Nonmonotonic Reasoning (LPNMR), Volume 8148 of LNCS, Corunna, Spain, pp. 79–91. Springer.Google Scholar
Balduccini, M. 2011. Industrial-size scheduling with ASP+CP. In Delgrande, J. and Faber, W. (Eds.), Logic Programming and Nonmonotonic Reasoning (LPNMR), Volume 6645 of LNCS, Vancouver, Canada, pp. 284–296. Springer.Google Scholar
Bhagyanath, A., Jain, T., and Schneider, K. 2016. Towards code generation for the synchronous control asynchronous dataflow (SCAD) architectures. In Wimmer, R. (Ed.), Methoden und Beschreibungssprachen zur Modellierung und Verifikation von Schaltungen und Systemen (MBMV), Freiburg, Germany, pp. 77–88. University of Freiburg.Google Scholar
Bhagyanath, A. and Schneider, K. 2016. Optimal compilation for exposed datapath architectures with buffered processing units by SAT solvers. In Leonard, E. and Schneider, K. (Eds.), Formal Methods and Models for Codesign (MEMOCODE), Kanpur, India, pp. 143–152. IEEE Computer Society.Google Scholar
Bhagyanath, A. and Schneider, K. 2017. Exploring the potential of instruction-level parallelism of exposed datapath architectures with buffered processing units. In Legay, A. and Schneider, K. (Eds.), Application of Concurrency to System Design (ACSD), Zaragoza, Spain, pp. 106–115. IEEE Computer Society.Google Scholar
Brain, M., Crick, T., De Vos, M., and Fitch, J. 2006. TOAST: Applying answer set programming to superoptimisation. In Etalle, S. and Truszczyński, M. (Eds.), International Conference on Logic Programming (ICLP), Volume 4079 of LNCS, Seattle, WA, USA, pp. 270–284. Springer.Google Scholar
Brewka, G., Niemela, I., and Truszczynski, M. 2003. Answer set optimization. In Gottlob, G. and Walsh, T. (Eds.), International Joint Conference on Artificial Intelligence (IJCAI), Acapulco, Mexico, pp. 867–872. Morgan Kaufmann.Google Scholar
Crick, T., Brain, M., De Vos, M., and Fitch, J. 2009. Generating optimal code using answer set programming. In Erdem, E., Lin, F., and Schaub, T. (Eds.), Logic Programming and Nonmonotonic Reasoning (LPNMR), Volume 5753 of LNCS, Potsdam, Germany, pp. 554–559. Springer.Google Scholar
De Angelis, E., Pettorossi, A., and Proietti, M. 2012. Synthesizing concurrent programs using answer set programming. Fundamenta Informaticae 120, 3–4 (July), 205–229.Google Scholar
Dodaro, C. and Maratea, M. 2017. Nurse scheduling via answer set programming. In Balduccini, M. and Janhunen, T. (Eds.), Logic Programming and Nonmonotonic Reasoning (LPNMR), Volume 10377 of LNCS, Espoo, Finland, pp. 301–307. Springer.Google Scholar
Feller, M. and Ercegovac, M. 1981. Queue machines: An organization for parallel computation. In Brauer, W., Brinch Hansen, P., Gries, D., Moler, C., Seegmüller, G., Stoer, J., Wirth, N., and Händler, W. (Eds.), Conpar 81, Volume 111 of LNCS, Nürnberg, Germany, pp. 37–47. Springer.Google Scholar
Gebser, M., Kaufmann, B., Neumann, A., and Schaub, T. 2007. clasp: A conflict-driven answer set solver. In Baral, C., Brewka, G., and Schlipf, J. (Eds.), Logic Programming and Nonmonotonic Reasoning (LPNMR), Volume 4483 of LNCS, Tempe, AZ, USA, pp. 260–265. Springer.Google Scholar
Guo, J., Limberg, T., Matus, E., Mennenga, B., Klemm, R., and Fettweis, G. 2006. Code generation for STA architecture. In Nagel, W., Walter, W., and Lehner, W. (Eds.), Euro-Par 2006 Parallel Processing, Volume 4128 of LNCS, Dresden, Germany, pp. 299–310. Springer.Google Scholar
Ishebabi, H., Mahr, P., Bobda, C., Gebser, M., and Schaub, T. 2009. Application of ASP for automatic synthesis of flexible multiprocessor systems from parallel programs. In Erdem, E., Lin, F., and Schaub, T. (Eds.), Logic Programming and Nonmonotonic Reasoning (LPNMR), Volume 5753 of LNCS, Potsdam, Germany, pp. 598–603. Springer.Google Scholar
Kumar, V. and Delgrande, J. 2009. Optimal multicore scheduling: An application of ASP techniques. In Erdem, E., Lin, F., and Schaub, T. (Eds.), Logic Programming and Nonmonotonic Reasoning (LPNMR), Volume 5753 of LNCS, Potsdam, Germany, pp. 604–609. Springer.Google Scholar
Lee, W., Barua, R., Frank, M., Srikrishna, D., Babb, J., Sarkar, V., and Amarasinghe, S. 1998. Space-time scheduling of instruction-level parallelism on a raw machine. In Bhandarkar, D. and Agarwal, A. (Eds.), Architectural Support for Programming Languages and Operating Systems (ASPLOS), San Jose, California, USA, pp. 46–57. ACM.Google Scholar
Schilling, T., Själander, M., and Larsson-Edefors, P. 2009. Scheduling for an embedded architecture with a flexible datapath. In IEEE Computer Society Annual Symposium on VLSI (ISVLSI), Tampa, FL, USA, pp. 151–156. IEEE Computer Society.Google Scholar
Schmit, H., Levine, B., and Ylvisaker, B. 2002. Queue machines: hardware compilation in hardware. In Arnold, J. and Pocek, K. (Eds.), Field-Programmable Custom Computing Machines (FCCM), Napa, California, USA, pp. 152–160. IEEE Computer Society.Google Scholar
Sethi, R. and Ullman, J. 1970. The generation of optimal code for arithmetic expressions. Journal of the ACM (JACM) 17, 4 (October), 715–728.Google Scholar
Smith, A., Burrill, J., Gibson, J., Maher, B., Nethercote, N., Yoder, B., Burger, D. and McKinley, K. 2006. Compiling for EDGE architectures. In Code Generation and Optimization (CGO), New York, New York, USA, pp. 185–195. IEEE Computer Society.Google Scholar
Äijö, T., Jääskeläinen, P., Elomaa, T., Kultala, H., and Takala, J. 2016. Integer linear programming-based scheduling for transport triggered architectures. ACM Transactions on Architecture and Code Optimization (TACO) 12, 4 (January), 59:1–59:22.Google Scholar