CMPE 513

ALGORITHMS IN VLSI DESIGN

by

Assist. Prof. Dr. Arda Yurdakul

Catalog Description:

Design methodologies in VLSI automation tools. High-level (behavioral) synthesis. Performance and power-efficient algorithms in architectural synthesis and optimization: module selection and allocation, scheduling. System-level synthesis. Architectures and algorithms for the automatic design of systems-on-chip, embedded systems: hardware/software partitioning, hardware/software synthesis, software design under hardware constraints.

Aim:

Today computer and electronics engineers work together to map lots of algorithms running on computers to hardware devices very efficiently so as to reduce real computation time and make everything portable. This course focuses on the well-known design targets and related algorithms of high-level VLSI design automation: Behavioral synthesis (i.e., algorithms for mapping a software onto an application specific hardware such as ASIC or FPGA), hardware-software co-design (i.e., algorithms for mapping a software onto a system consisting of application specific hardware and a number of processors) and software design under hardware constraints such as timing and power. Software design under power constraints is a very hot issue in VLSI design automation because of battery-powered portable computing and wireless communication protocols.

Tentative Course Outline:
Introduction to Design Methodologies.
A Quick Tour of VLSI Design Automation Tools.

Basic Issues in Combinatorial Optimization

Behavioral (High-level) Synthesis.

• Architectural Synthesis and Optimization Issues

• Module Selection and Allocation
• Scheduling
• Synthesis and Optimization for Low-Power

Hardware-Software Co-design

• Co-Design Systems.
• Embedded Systems.
• Hardware/Software Partitioning.
• Hardware/Software Co-Synthesis.

Software Design under Hardware Constraints

Textbooks:

Synthesis and Optimization of Digital Circuits

Giovanni DeMicheli,

McGraw Hill, ISBN 0-07-016333-2, 1994

Low-Power CMOS VLSI Circuit Design

Kaushik Roy, Sharat C. Prasad,

John Wiley & Sons, ISBN 0-471-11488-X, 2000.

Hardware/Software Co-Design for Data Flow Dominated Embedded Systems

Ralf Niemann,

Kluwer Academic Publishers, ISBN 0-7923-8299-4, 1998

Embedded Multiprocessors-Scheduling and Synchronization
Sundararajan Sriram ; Shuvra S. Bhattacharyya
MARCEL DEKKER AG, ISBN: 0-8247-9318-8, 2000

Recent papers in the literature!

Prerequisite: Good programming experience in one of the high-level languages like C, Pascal.

Evaluation: Weekly computer homework and a final project.