Here you can find the course material for the Algorithms in Hardware Design research-oriented, seminar-style course as it was given in the fall semester of 2024/25. The idea was to introduce the students to fundamental concepts from logic synthesis, technology mapping, placement, and routing through a small number of lectures and then to proceed with reading select papers from these areas. The papers were chosen not only based on the historical impact that they had, but also on the appropriateness of the ideas that they present for someone with little to no experience in reading papers and conducting research. In particular, I tried to select groups of papers in which a logical progression of ideas could be observed.

The students were all tasked with reviewing each paper, through a HotCRP website set up for the course itself and using a review template from one of the top FPGA conferences. Then, each week, two students would volunteer to present one of the papers as if it were their own. Discussions would follow after each presentation. Finally, each student would chose an open question related to one of the algorithms that we covered, either from a list that I prepared (making sure that it is actually possible to do something useful about the question during the course of a semester, and without much or any prior research experience; for example, some of the options were to analyze the sensitivity of the results on some parameter of the chosen heuristic), or based on something that they observed. The idea was that we would simulate lab meetings in class, discussing results and ideas that each student had while working on their project. Unfortunately, due to the political situation in Serbia since November 2024 and its impact on the teaching process, we were not able to make much progress on this front.

I thoroughly enjoyed giving these lectures, listening to the presentations of the students and participating in the ensuing discussions with them. The whole idea was to give the students a glimpse of what it means to do research in an applied field of computer science, and to train them in reading and reviewing papers, which I think could benefit the entire research community a lot. At least some of the students are already actively participating in research so I would say that we were successful. The class was rather small, but the students were amazing, so I really look forward to the next iteration of the course.

All the slides are in Serbian (or a mixture of English and Serbian), as this is an undergraduate course, which means that teaching in Serbian is mandatory. Hopefully, with the help of some automatic translation tool, you will be able to find your way through the contents. Of course, in case you have any questions, don’t hesitate to contact me.

It is also likely that the slides contain mistakes, as they were used only once. If you find some, I would appreciate if you could email me with the details. Finally, feel free to use any of this material for your own teaching, but I would appreciate if you acknowledged thait.

Reading list

1. Haaswijk et al. SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism. TCAD, 2020
2. Mishchenko et al. Improvements to Technology Mapping for LUT-Based FPGAs. TCAD, 2007
3. Marquardt et al. Using Cluster-Based Logic Blocks and Timing-Driven Packing to Improve FPGA Speed and Density. FPGA, 1999
4. Chen et al. Improving Timing-Driven FPGA Packing with Physical Information. FPL, 2007
5. Marquardt et al. Timing-Driven Placement for FPGAs. FPGA, 2000
6. Vorwerk et al. Improving Annealing via Directed Moves. FPL, 2007
7. Murray and Betz. Adaptive FPGA Placement Optimization via Reinforcement Learning. MLCAD, 2019
8. Nair. A Simple Yet Effective Technique for Global Wiring. TCAD, 1987
9. McMurchie and Ebeling. PathFinder: A Negotiation-Based Performance-Driven Router for FPGAs. FPGA, 1995
10. Rubin and DeHon. Timing-Driven Pathfinder Pathology and Remediation: Quantifying and Reducing Delay Noise in VPR-Pathfinder. FPGA, 2011

Slides

1. Introduction (How Computer Hardware is Created?)
2. Basic Principles of Logic Synthesis (Part 1)
3. Basic Principles of Logic Synthesis (Part 2)
4. Technology Mapping
5. Placement and Routing