Using minimal minterms to represent programmability

ABSTRACT

We address the problem of formally representing the programmability of a system. We define the programmability of a system as the set of valid execution paths that can be configured statically by software. We formally represent this programmability as a Boolean function. From this representation, we extract a subset of on-set minterms that we call minimal minterms. We prove that these minimal minterms represent the set of smallest schedulable atomic actions of the system, and that we can use a special generator relation to determine if subsets of these actions can be executed in parallel. We also prove that given an arbitrary Boolean function we can extract the minimal minterms and recreate the entire on-set by applying the generator relation to every element of the power set of the set of minimal minterms. Thus, the minimal minterms represent the complete instruction set supported by the system, and the generator relation represents the inherent parallelism among the instructions. Furthermore, we automatically generate the required software development tools and hardware implementation from this representation of programmability. Finally, we show that we can efficiently compute the minimal minterms and apply the generator relation to verify parallel executions on interesting data path systems.

REFERENCES

• 1: Scott J. Weber , Matthew W. Moskewicz , Matthias Gries , Christian Sauer , Kurt Keutzer, Fast Cycle-Accurate Simulation and Instruction Set Generation for Constraint-Based Descriptions of Programmable Architectures, Proceedings of the International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS'04), p.18-23, September 08-10, 2004 [doi>10.1109/CODES+ISSS.2004.29]
• 2: H. Tomiyama, A. Halambi, P. Grun, N. Dutt, and A. Nicolau. "Architecture Description Languages for Systems-on-Chip Design." In APCHDL'99, 109--116.
• 3: Andreas Hoffmann , Heinrich Meyr , Rainer Leupers, Architecture Exploration for Embedded Processors with Lisa, Kluwer Academic Publishers, Norwell, MA, 2002
• 4: Ashok Halambi , Peter Grun , Vijay Ganesh , Asheesh Khare , Nikil Dutt , Alex Nicolau, EXPRESSION: a language for architecture exploration through compiler/simulator retargetability, Proceedings of the conference on Design, automation and test in Europe, p.100-es, January 1999, Munich, Germany [doi>10.1145/307418.307549]
• 5: Johan van Praet , Dirk Lanneer , Gert Goossens , Werner Geurts , Hugo de Man, A Graph Based Processor Model for Retargetable Code Generation, Proceedings of the 1996 European conference on Design and Test, p.102, March 11-14, 1996
• 6: Rainer Leupers, Retargetable Code Generation for Digital Signal Processors, Kluwer Academic Publishers, Norwell, MA, 1997
• 7: R. L. Rudell and A. Sangiovanni-Vincentelli, "Multiple-Valued Minimization for PLA Optimization", TCAD, Vol. CAD-6, No. 5, Sept. 1987, 727--751.
• 8: R. J. Bayardo Jr. and R. Schrag. "Using CSP look-back techniques to solve exceptionally hard SAT instances." In Proc. of the Second Int'l Conf. on Principles and Practice of Constraint Programming (Lecture Notes in Computer Science 1118), Springer, 1996, 46--60.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Boolean function representation, Boolean satisfiability, instruction set extraction