Human computing for EDA

ABSTRACT

Electronic design automation is a field replete with challenging -- and often intractable -- problems to be solved over very large instances. As a result, the field of design automation has developed a staggering expertise in approximations, abstractions and heuristics as a means to side-step the NP-hard nature of these problems. Approximations and heuristics are at heart a natural application of human reasoning. In this work we propose to harness human potential to solve some of these problems. Specifically, we propose FunSAT, a massively multi-player puzzle game for SAT solving. FunSAT leverages visual pattern recognition skills, abstract perception and intuitive strategy skills of humans to solve complex SAT instances. Players are motivated by the puzzle-solving challenges of the game and by its social interaction aspects.

REFERENCES

• 1: Online game playing is still the most popular online activity. Associated Content, 17 August 2007. www.associatedcontent.com.
• 2: PC stripper helps spam to spread. BBC News, 30 October 2007. www.news.bbc.co.uk.
• 3: WoW surpasses 10 million subscribers, now half the size of australia. Joystiq, 22 January 2008. www.joystiq.com.
• 4: Amazon. Mechanical turk, 2008. www.mturk.com.
• 5: J. Hawkins and S. Blakeslee. On Intelligence. Owl Books, 2005.
• 6: L. von Ahn. Games with a purpose. IEEE Computer, 39(6):92--94, June 2006.
• 7: L. von Ahn and L. Dabbish. Labeling images with a computer game. In ACM SIGCHI, pages 319--326, 2004.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Verification

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human information processing

General Terms:
Human Factors, Verification

Keywords:
human computing, satisfiability