Incorporating imprecise computation into system-level design of application-specific heterogeneous multiprocessors

ABSTRACT

This paper introduces a basic mixedinteger-linear model (MILP) to design application-specificheterogeneous multiprocessors (ASHM) allowingimprecise computation of tasks executed ina non-preemptive mode.The proposed model wasused in the development of a genetic algorithm integratedinto the tool set MEGA that uses soft computingtechniques for design of optimal/near-optimalASHMs subject to constraints on performance, costand output-data quality.

REFERENCES

• 1: Stewart Brand, The media lab: inventing the future at MIT, Penguin Books, New York, NY, 1988
• 2: CHU, W. W., HOLLAWAY, L.J. and EFE, K., "Task Allocation in Distributed Data Processing", Computer, Vol. 13, No. 11, pp. 57-69, Nov 1980.
• 3: Jen-Yao Chung , Jane W. S. Liu , Kwei-Jay Lin, Scheduling Periodic Jobs that Allow Imprecise Results, IEEE Transactions on Computers, v.39 n.9, p.1156-1174, September 1990 [doi>10.1109/12.57057]
• 4: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 5: HO, K., LEUNG, J. Y-T. and WEI, W-D., "Minimizing Maximum Weighted Error for Imprecise Computation Tasks", Technical Report UNL-CSE-92-017, Dept. of Computer Science and Eng., University of Nebraska, Lincoln, 1992.
• 6: E. S. H. Hou , N. Ansari , H. Ren, A Genetic Algorithm for Multiprocessor Scheduling, IEEE Transactions on Parallel and Distributed Systems, v.5 n.2, p.113-120, February 1994 [doi>10.1109/71.265940]
• 7: Jane W. S. Liu , Kwei-Jay Lin , Wei-Kuan Shih , Albert Chuang-shi Yu , Jen-Yao Chung , Wei Zhao, Algorithms for Scheduling Imprecise Computations, Computer, v.24 n.5, p.58-68, May 1991 [doi>10.1109/2.76287]
• 8: Zbigniew Michalewicz, Genetic algorithms + data structures = evolution programs (2nd, extended ed.), Springer-Verlag New York, Inc., New York, NY, 1994
• 9: PETERSON, L. (editor), Proc. of the 1996 Heterogeneous Computing Workshop, IEEE Computer Press, 1996.
• 10: PRAKASH, S. and PARKER, A. C., "SOS" Synthesis of Application Specific Heterogeneous Multiprocessor Systems", J. of Par. and Distributed Comp., No. 16, pp. 338-351, Dec. 1992.
• 11: RAVIKuMAR, C. P. and GUPTA, A. K.,"Genetic Algorithm for mapping tasks onto a reconfigurable parallel processor", IEE Proc. in Comp. Dig. Tech., vol. 142, no. 2, pp. 81-86, March 1995.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  C. Computer Systems Organization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Measurement, Performance, Theory