Abstract
Placement and scheduling are recognized as the most important problems when exploiting the benefit of partially reconfigurable devices such as FPGAs. For example, dynamically loading and unloading modules onto an FPGA causes fragmentation, and—in turn—may decrease performance. To counteract this effect, we use methods from algorithmics and mathematical optimization to increase the performance and present algorithms for placing, scheduling, and defragmenting modules on FPGAs. Taking communication between modules into account, we further present strategies to minimize communication overhead. Finally, we consider scheduling module requests with time-varying resource demands.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahmadinia, A., Teich, J.: Speeding up online placement for XILINX FPGAs by reducing configuration overhead. In: Proc. IFIP Internat. Conf. VLSI-SOC, pp. 118–122 (2003)
Ahmadinia, A., Bobda, C., Bednara, M., Teich, J.: A new approach for on-line placement on reconfigurable devices. In: Proc. Internat. Parallel Distr. Proc. Sympos., p. 134 (2004)
Ahmadinia, A., Bobda, C., Fekete, S., Teich, J., van der Veen, J.: Optimal routing-conscious dynamic placement for reconfigurable devices. In: Internat. Conf. Field-Programm. Logic Appl., pp. 847–851 (2004)
Ahmadinia, A., Bobda, C., Ding, J., Majer, M., Teich, J., Fekete, S., van der Veen, J.: A practical approach for circuit routing on dynamically reconfigurable devices. In: Proc. 16th IEEE Internat. Workshop Rapid System Prototyping (RSP), pp. 84–90 (2005)
Baker, B.S., Schwarz, J.S.: Shelf algorithms for two-dimensional packing problems. SIAM J. Comput. 12(3), 508–525 (1983)
Bazargan, K., Kastner, R., Sarrafzadeh, M.: Fast template placement for reconfigurable computing systems. IEEE Des. Test Comput. 17, 68–83 (2000)
Becker, T., Luk, W., Cheung, P.Y.: Enhancing relocatability of partial bitstreams for run-time reconfiguration. In: Proc. 15th Annu. Sympos. Field-Programm. Custom Comput. Mach., pp. 35–44 (2007)
Bender, M.A., Demaine, E.D., Farach-Colton, M.: Cache-oblivious B-trees. SIAM J. Comput. 35, 341–358 (2005)
Bender, M.A., Fineman, J.T., Gilbert, S., Kuszmaul, B.C.: Concurrent cache-oblivious B-trees. In: Proc. 17th Annu. ACM Sympos. Parallel. Algor. Architect., pp. 228–237 (2005)
Bobda, C., Ahmadinia, A., Majer, M., Teich, J., Fekete, S., van der Veen, J.: DyNoC: A dynamic infrastructure for communication in dynamically reconfigurable devices. In: Internat. Conf. Field-Programmable Logic and Applications, pp. 153–158 (2005)
Bromley, G.: Memory fragmentation in buddy methods for dynamic storage allocation. Acta Inform. 14, 107–117 (1980)
Caprara, A., Salazar-Gonzalez, J.J.: Laying out sparse graphs with provably minimum bandwidth. INFORMS J. Comput. 17, 356–373 (2005)
Compton, K., Li, Z., Cooley, J., Knol, S., Hauck, S.: Configuration relocation and defragmentation for run-time reconfigurable systems. IEEE Trans. VLSI 10, 209–220 (2002)
Diessel, O., ElGindy, H., Middendorf, M., Schmeck, H., Schmidt, B.: Dynamic scheduling of tasks on partially reconfigurable FPGAs. IEEE Proc. Comput. Dig. Tech. 147, 181–188 (2000)
Fekete, S.P., Schepers, J.: New classes of lower bounds for the bin packing problem. Math. Program. 91, 11–31 (2001)
Fekete, S.P., Schepers, J.: A combinatorial characterization of higher-dimensional orthogonal packing. Math. Oper. Res. 29, 353–368 (2004)
Fekete, S.P., Schepers, J.: A general framework for bounds for higher-dimensional orthogonal packing problems. Math. Methods Oper. Res. 60, 311–329 (2004)
Fekete, S.P., Köhler, E., Teich, J.: Optimal FPGA module placement with temporal precedence constraints. In: Proc. Design Automat. Test Europe (DATE), pp. 658–665 (2001)
Fekete, S.P., van der Veen, J.C., Majer, M., Teich, J.: Minimizing communication cost for reconfigurable slot modules. In: Proceedings of 16th International Conference on Field Programmable Logic and Applications (FPL06), pp. 535–540 (2006)
Fekete, S.P., Schepers, J., van der Veen, J.: An exact algorithm for higher-dimensional orthogonal packing. Oper. Res. 55, 569–587 (2007)
Fekete, S.P., Kamphans, T., Schweer, N., Tessars, C., van der Veen, J.C., Angermeier, J., Koch, D., Teich, J.: No-break dynamic defragmentation of reconfigurable devices. In: Proc. 18th Internat. Conf. Field Programm. Logic Appl., pp. 113–118 (2008)
Fekete, S.P., van der Veen, J.C., Ahmadinia, A., Göhringer, D., Majer, M., Teich, J.: Offline and online aspects of defragmenting the module layout of a partially reconfigurable device. IEEE Trans. VLSI 16, 1210–1219 (2008)
Fekete, S.P., Kamphans, T., Schweer, N.: Online square packing. In: Proc. 20th Algorithms and Data Structure Symposium (WADS), Banff, Alberta, Canada, pp. 302–314
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Gericota, M.G., Alves, G.R., Silva, M.L., Ferreira, J.M.: Run-time defragmentation for dynamically reconfigurable hardware. In: New Algorithms, Architectures and Applications for Reconfigurable Computing (2005)
Grötschel, M.: On the symmetric travelling salesman problem: solution of a 120-city problem. Math. Program. Study 12, 61–77 (1980)
Hagemeyer, J., Kettelhoit, B., Koester, M., Porrmann, M.: Design of homogeneous communication infrastructures for partially reconfigurable FPGAs. In: Proc. Internat. Conf. Engineering of Reconf. Systems and Algor., Las Vegas, USA (2007)
Hirschberg, D.S.: A class of dynamic memory allocation algorithms. Commun. ACM 16, 615–618 (1973)
Knowlton, K.C.: A fast storage allocator. Commun. ACM 8, 623–625 (1965)
Knuth, D.E.: The Art of Computer Programming: Fundamental Algorithms, 3rd edn. vol. 1, Addison–Wesley, Reading (1997)
Koch, D., Ahmadinia, A., Bobda, C., Kalte, H.: FPGA architecture extensions for preemptive multitasking and hardware defragmentation. In: Proc. IEEE Internat. Conf. Field-Programmable Technology, Brisbane, Australia, pp. 433–436 (2004)
Koch, D., Beckhoff, C., Teich, J.: ReCoBusBuilder—a novel tool and technique to build static and dynamically reconfigurable systems for FPGAs. In: Proc. 18th Internat. Conf. Field Programm. Logic Appl., pp. 119–124 (2008)
Koester, M., Kalte, H., Porrmann, M., Ruckert, U.: Defragmentation algorithms for partially reconfigurable hardware. Int. Fed. Inf. Process. Publ.-IFIP 240, 41 (2007)
Kuon, I., Rose, J.: Measuring the gap between FPGAs and ASICs. IEEE Trans. CAD Integr. Circuits Syst. 26, 203–215 (2007)
Lawler, E.L., Lenstra, J.K., Rinooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: Algorithms and complexity. In: Graves, S.C., Rinnooy Kan, A.H.G., Zipkin, P.H. (eds.) Logistics of Production and Inventory. Handbooks in Operations Research and Management, vol. 4, pp. 445–522. North–Holland, Amsterdam (1993)
Lysaght, P., Blodget, B., Mason, J., Young, J., Bridgford, B.: Invited paper: Enhanced architecture, design methodologies and CAD tools for dynamic reconfiguration of Xilinx FPGAs. In: Proc. 16th Internat. Conf. Field Programm. Logic Appl., pp. 1–6 (2006)
Majer, M., Bobda, C., Ahmadinia, A., Teich, J.: Packet routing in dynamically changing networks on chip. In: Proc. Internat. Parallel Distr. Proc. Sympos. (IPDPS), p. 154 (2005)
Martello, S., Monaci, M., Vigo, D.: An exact approach to the strip-packing problem. INFORMS J. Comput. 15(3), 310–319 (2003)
Seiden, S.S.: On the online bin packing problem. J. ACM 49(5), 640–671 (2002). doi:10.1145/585265.585269
Shi, J., Bhatia, D.: Performance driven floorplanning for FPGA based designs. In: Internat. Sympos. Field Programm. Gate Arrays, pp. 112–118 (1997)
Steiger, C., Walder, H., Platzner, M.: Operating systems for reconfigurable embedded platforms: Online scheduling of real-time tasks. IEEE Trans. Comput. 53, 1393–1407 (2004)
Teich, J., Fekete, S., Schepers, J.: Compile-time optimization of dynamic hardware reconfigurations. In: Internat. Conf. Parallel Distr. Proc. Techn. Appl., pp. 1097–1103 (1999)
Teich, J., Fekete, S.P., Schepers, J.: Optimal hardware reconfiguration techniques. J. Supercomput. 19, 57–75 (2001)
Tessier, R.G.: Fast place and route approaches for fpgas. PhD thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science (1999)
van der Veen, J., Fekete, S., Majer, M., Ahmadinia, A., Bobda, C., Hannig, F., Teich, J.: Defragmenting the module layout of a partially reconfigurable devices. In: Plaks, T.P. (ed.) Proc. Internat. Conf. Engin. Reconf. Syst. Algor., pp. 92–101 (2005)
Walder, H., Platzner, M.: Online scheduling for block-partitioned reconfigurable devices. In: Proc. Design Automat. Test Europe (DATE), pp. 290–295 (2003)
Yang, X., Wang, M., Kastner, R., Ghiasi, S., Sarrafzadeh, M.: Fast placement approaches for FPGAs. ACM Trans. Des Automat. Electr. Syst. 8, 316–333 (2003)
Yuh, P.H., Yang, C.L., Chang, Y.W.: Temporal floorplanning using the T-tree formulation. In: Proc. Internat. Conf. Comput. Aided Design, pp. 300–305 (2004)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer Science+Business Media B.V.
About this chapter
Cite this chapter
Ahmadinia, A. et al. (2010). ReCoNodes—Optimization Methods for Module Scheduling and Placement on Reconfigurable Hardware Devices. In: Platzner, M., Teich, J., Wehn, N. (eds) Dynamically Reconfigurable Systems. Springer, Dordrecht. https://doi.org/10.1007/978-90-481-3485-4_10
Download citation
DOI: https://doi.org/10.1007/978-90-481-3485-4_10
Published:
Publisher Name: Springer, Dordrecht
Print ISBN: 978-90-481-3484-7
Online ISBN: 978-90-481-3485-4
eBook Packages: EngineeringEngineering (R0)