Emerging Computing Technologies KAIST Web Page of Marek Perkowski

PART 1. REVERSIBLE LOGIC

1. Lecture 1.1. Introduction to class. Administrativia. Background. Very short review of Karnaugh Maps. SOP logic. Covering. EXor Logic. ESOP circuits.
   
2. Lecture 1.2 on History of Computers.
   
3. Lecture 1.2 continued. Current research issues. Molecular, DNA and Quantum Computing
   
4. Lecture 1.3 on Reversible logic and reversible gates.
   
5. Lecture 1.3 (continued) on representation and analysis of reversible circuits
   
6. Lecture 1.4 on Billiard Ball model of reversible computing and Optical Reversible and Conservative Circuits.
7. Lecture 1.5 on Davio expansions, Davio gates and Kronecker Functional Decision Diagrams.
8. Lecture 1.6 on synthesis of reversible circuits with garbage bits.
   After these lectures you can start your individual research. Please contact me if you are interested. I will be always happy to talk to you and discuss your particular area of interest.
   AUXILIARY READING MATERIAL FOR REVERSIBLE LOGIC
   1. D. Maslov and G. Dueck, "Garbage in Reversible Designs of Multiple Output Functions". PDF
   2. D.Maslov, G. Dueck and D.M. Miller, "Templates for Toffoli Networks Synthesis", PDF
   3. D.M.Miller and G.W.Dueck, "Spectral Techniques for Reversible Logic Synthesis", PDF
   4. D. Maslov and G.W. Dueck,"Asymptotically Optimal Regular Synthesis of Quantum Networks, PDF
   5. G.W. Dueck and D. Maslov, "Reversible Function Synthesis with Minimum Garbage Outputs", PDF
   6. D.M. Miller, D. Maslov, and G.W. Dueck, "A Transformation Based Algorithm for Reversible LOgic Synthesis, PDF
   7. G.w.Dueck, D. Maslov, and D.M. Miller, "Transformation-based Synthesis of Networks of Toffoli/Fredkin Gates, PDF
   8. Ideas about regularity in reversible logic. PDF format.
   9. Paper by Pawel Kerntopf on reversible logic. PDF format.
   10. Ultra Large Scale LSI (ULSI) Symposium paper. Ideas can be used on exam. PDF format.
   11. Paper by Perkowski et al about regular reversible logic. Source of ideas for exams and homeworks. PDF format.
   12. New paper about reversible logic. Source of class ideas and for projects. PDF format.
   13. A new paper about ESOP circuit synthesis for increased testability. PDF format.
   14. Introduction and Overview of Multiple-Valued Logic. PDF format.
   
   Reading the auxiliary materials is not mandatory but may be useful for problem solving, homeworks and exams. It is recommended to read those that are mentioned in class by professor. We will use the information on reversible logic when we will be discussing quantum and optical circuits, for instance.

PART 2. CELLULAR AUTOMATA PROJECT

1. Lecture 2.1. Introduction to Cellular Automata and Artificial Life

PART 3. MIDTERM EXAMINATION PREPARATION

1. Problems that may appear in Midterm Exam. PDF.
2. Midterm Examination problems. PDF format.
3. Exam problems Solutions.

PART 4. FIELD PROGRAMMABLE GATE ARRAYS (FPGAs) AND RECONFIGURABLE COMPUTERS.

1. Lecture 4.1. on VLSI realization, Complex Programmable Logic Devices(CPLDs) and FPGAs. PDF format.
2. Lecture 4.2. Introduction to systolic processors. Can be used in homeworks and exams. More examples will be given on additional meetings. PDF format.
3. Lecture 4.3. Systolic Processors. PDF format.
4. Lecture 4.4. Reconfigurable Pipelines. PDF format.
5. Lecture 4.5. More detailed examples of systolic processors
   PDF format
6. Materials for homeworks and projects about parallel structures
   PDF format
   AUXILIARY READING MATERIAL FOR REGULAR LOGIC AND CELLULAR AUTOMATA
   • 1. Hough Transform. This transform, or rather family of transforms has practical applications in industrial and military computer vision. It is a big challenge to design a fast Hough transform in hardware, so many challenging projects related to pipelined, systolic or parallel realization of Hough Transforms are possible. You can expect similar problems on final exam.
     1. Hough and Canny operators for Image Processing. PDF format.
     2. Hough-Transform.pdf
     3. Hough-Transformation.pdf
     4. Hough Transform Fundamentals. PDF format.
     5. Application of Hough Transform in Astronomy to detect craters. PDF format.
        
   • 2. Satisfiability Engines, Petrick Function Solvers and Hardware Boolean Solvers This is another class of challenging problems for parallelization and systolization.
     Design of regular hardware for SAT engine. PDF format.
   • 3. DNA Processors These processors are used for matching and other operations in DNA engineering.
     Systolic Processor for DNA. PDF format.
   • 4. Standard Systolic Architectures for matrices and vectors.
     • Analysis of systolic convolution.
       PDF format.
       PPT format
       
     • Systolic Matrix Multiplication.
       PDF format
       PPT format
       
     • Lecture about systolic architectures with good matrix and vector manipulation examples.
       PDF format.
       PPT format.
       
     • Lecture about parallel processing and systolic architectures with good examples.
       PPT format.
       
     • Parallel algorithms and systolic processors.
       PDF format.
       PPT format.
       
     • Reconfigurable parallel architectures - examples of systolic.
       PDF format.
       PPT format.
       
     • Paper about Hardware Based Realization of Genetic Algorithm.
       PDF format.
       
     • Special-Purpose Mesh Architectures - examples of Systolic.
       PDF format.
       PPT format.
       
     • Lecture of Andre de Hon from Caltech about Systolic Architectures. Examples!!
       PDF format.
       PPT format.
       
   • 4. Digital Signal Processors and Image Processors
     • lecture 015. DSP-circuits. PDF format.
     • Morphological Image Processing. This is useful as a background material for designing regular structures and cellular automata for image processing. Good for exams and various projects. PDF format.
     • Parallel Processors Classification. Useful for various design projects in technologies presented in this class. PDF format.
   • 6. Design of new types of FPGAs, EPLDs and configurable boards.
     • XC6200 chip from Xilinx. Example of chip architecture used in Evolvable Hardware and Brain Building. PDF format. Project and homework related. PDF format.
     • Systematic design of FPGAs using BDDs. PDF format.
     • Chong Ho Lee. Slides to lecture about self-repairable FPGA. Statistical analysis of improved reliability. PDF format.
     • DEC-PERLE reconfigurable processor board. Example of very successful early FPGA-based computer with many supercomputer applications. Good for projects. PDF format.

PART 5. EVOLUTIONARY ALGORITHMS AND EVOLVABLE HARDWARE.

1. Lecture 5.1. Evolutionary Algorithms. PDF format.
2. Lecture 5.2. Evolutionary-algorithms 2. PDF format.
3. Lecture 5.3. Evolutionary Algorithms 3. PDF format.
   AUXILIARY READING MATERIAL FOR EVOLUTIONARY ALGORITHMS AND EVOLVABLE HARDWARE
   1. Genetic Algorithms for Logic Synthesis. PDF format.
   2. Evolvable Hardware 001. PDF format.
   3. Evolvable Hardware 004. PDF format.
   4. Evolvable Hardware 006. PDF format.
   5. Embriology ideas in hardware. Hardware that grows and adapts. Part of Evolvable Hardware, link to DNA and future technologies. Good for projects. PDF format.
   6. Extrinsic Evolvable Hardware. Examples and Definitions. Source of project ideas. PDF format.
   7. Intrinsic Evolvable Hardware. Examples of systems. Systems designed at PSU. Source of ideas useful for exams and homeworks. PDF format.
   8. Evolvable Hardware. FPGA realization. Source of ideas about FPGA architectures, FPGA design and their use in reconfigurable, and adaptable architectures. PDF format

PART 6. CELLULAR AUTOMATA.

• Paper about realizing computer architecture using quantum dot technology.
  PDF format.
  
• Lecture 6.1. Three-Dimensional Cellular Logic Illustration.
  PDF format
  
• Lecture 6.2. Logic of Quantum Dot Cellular Automata.
  PDF format
  
• Lecture 6.3. Cellular morphogenesis.
  PDF format.
  
• Lecture 6.4. Cellular Automata. Random Number Generation. Encryption.
  PDF format.
  
• Lecture 6.5. About CA-based Random Number Generation, Cryptography and Cellular Reversible Automata
  PDF format
  
• Lecture 6.6. Lecture by Norm Margolus about Physical Reversible Models
  PDF format
  
• Lecture 6.7. Lecture 2 by Norm Margolus
  PDF format
  
• Lecture 6.8. Lecture 3 by Norm Margolus
  PDF format
  
• Lecture 6.9. Lecture by Michael Frank about reversible processors from MIT
  PDF format
  
• Lecture 6.10. Lecture about Von Neumann self-reproducing automata
  PPT format
  
• An interesting example of hexagonal systolic architecture - different than those from the class.
  PDF format.
  

AUXILIARY MATERIALS ABOUT REGULAR STRUCTURES AND CELLULAR AUTOMATA
• M.Perkowski, M. Chrzanowska-Jeske and Y.Xu, "Lattice Diagrams Using Reed-Muller Logic", PDF. This paper explains how arbitrary combinational function can be mapped to lattice structures. The method can be extended to multi-output functions, finite state machines and cellular automata.
  
• Paper to read about expansion to lattices to be used in reversible cellular computing. PDF.
  
• Paper about reversible cellular structures. TO be published soon, you may contribute to extensions and improvements of these ideas .
  
• Buller and Perkowski. 2003. Paper about cellular automata realization of elementary reversible circuits. Easy to understand. New research.
  Word format
  PDF format
  

PART 7. QUANTUM COMPUTING

1. Lecture 7.1. Motivation and Introduction to Quantum Computing.
   PDF Format
   
2. Lecture 7.2. On Computer Science related to Quantum Computing. Mostly undecidability and complexity.
   PDF Format
   
3. Lecture on algebra used in quantum computing
4. Quantum gates and Circuits
5. Deutsch, Shorr and Grover algorithms.
6. Quantum Communication and Cryptography.
7. Physical Realization of Quantum Computers.
8. Quantum Computational Intelligence.
   
   
   AUXILIARY MATERIALS ABOUT QUANTUM COMPUTING AND COMPLEXITY
   1. Computational Complexity. To Lecture 7.2.
      Review of Post and Markov algorithms in PDF format.
      Review of Predicate Calculus in PDF format.
      
   2. Buller. Elementary introduction to quantum circuits with calculated examples. To Lecture 7.1.
      Word format
      PDF Format
   3. Goran Proposal. PDF format.
   4. Goran Proposal 1. PDF format.
   5. Recent paper about multiple-valued quantum logic synthesis. Useful for definition of new quantum gates and their use in synthesis. PDF format.
   6. Paper by Mozammel Khan, Perkowski and Kerntopf for ISMVL 2003 conference. PDF format.
   7. Very interesting paper by Abrams et al that links P=NP problem solution to non-linearity versus linearity of quantum mechanics. PDF format.
      
      
   8. Student Hyunkoo Jee found this interesting information about a new important discovery, which I did not cover in class. It may lead to new non-quantum factorization algorithms and to new discoveries in quantum computing as well.
      Three Indean computer-scientests found an algotithm that can distinguish whether a given number is prime or not... (primality test problem) in P (ploynomial time). It is a deterministic algorithm (not stochastic!).
      Here is an introduction page (It's in Korean language, but the important part is written in English). Internet Information 1.
      And here is an article in 'Science Magazine'
      Internet Information 2.
      And here is the original webpage from the inventers of the algorithm. This page contains full material about this (including the original papers)
      Internet Information 3.