Crowdsourcing the Complexities of Electronic Design Automation

Featured document Crowd Creativity, Distributed Knowledge

IEEE Spectrum: Crowdsourcing the Complexities of Electronic Design Automation

Page 1 of 2

SEMICONDUCTORS

// DESIGN

NEWS

Crowdsourcing the Complexities of Electronic Design Automation

Researchers develop an online game that may one day help chipmakers improve their designs
BY JOSHUA ROMERO // JULY 2009

30 July 2009—Electronic design automation (EDA) is full of large, intricate problems. Figuring out the best way to arrange transistors on a chip, for example, becomes exponentially more complex as the number of transistors increases. Computer scientists have made great strides in developing algorithms that can solve many of these problems, but a team of researchers at the University of Michigan, in Ann Arbor, believes that the industry could benefit from a different resource: human intuition. “These kinds of problems are difficult for computers to solve. We started by thinking, ‘How can humans help electronic design automation?’ ” says Valeria Bertacco, an associate professor in computer science and engineering. She and Andrew DeOrio, a doctoral student, have developed an online game that challenges players to take on a type of problem common in design automation. They presented their idea of human-assisted problem solving today at the Design Automation Conference, in San Francisco. In large, complex EDA problems, there are initially millions of possible paths to a solution. It’s similar to a maze: At the beginning, you have to pick an initial path to explore and see where it leads. The problem for designers is that the number of solution paths increases exponentially with the number of variables. Even the best algorithms can get tripped up if they start down a search path with no possible solution. Bertacco and DeOrio’s game simulates ”satisfiability problems,” a common class of problem encountered in EDA. A satisfiability problem consists of a number of Boolean expressions that must be simultaneously satisfied and a number of variables that may be either true or false. As an example, consider a Boolean expression with two variables, x and y , satisfied only when x and y are different. There are two ways to satisfy this particular expression: by assigning x as true and y as false, or vice-versa. But other expressions may depend on the assignment of x as well. Satisfiability problems are often an important part of the design verification stage of chip design. For example, they are used to find out what input combinations result in exposing a potential bug in the design. If no such combination exists, then the designers don’t have to worry about that particular bug.

http://spectrum.ieee.org/semiconductors/design/crowdsourcing-the-complexities-of-electronic 8/6/2009

IEEE Spectrum: Crowdsourcing the Complexities of Electronic Design Automation

Page 2 of 2

Modern satisfiability solvers tend to prioritize and limit their searches to a few paths that look promising. By using this method, however, they don’t always find the best configuration. What humans lack in brute-force speed, they tend to make up for with pattern recognition and intuition—the ability to know a good move without being able to explain why it’s good. And, most important, they like to play games. Take the game of Go, for instance. Humans can still easily beat the best software, because of creative thinking and visual reasoning. In Bertacco and DeOrio’s game, satisfiability problems are translated to an array of buttons and bubbles. Each bubble represents a Boolean expression and turns green when satisfied. Players toggle the state of numerous buttons until all the bubbles are green. The game play closely resembles that of Lights Out and should appeal to fans of Minesweeper or Sudoku. Adding a human component is a new idea in the EDA world, and Bertacco eagerly awaits the response of her colleagues. But the idea of harnessing human computing power has already proved valuable in other fields. For instance, reCAPTCHA (which IEEE Spectrum uses in its Web site’s comment section to stop spam) exploits a human’s superior ability to pull information from distorted images. NASA has used a similar approach to image analysis: In its Clickworkers program, volunteers identify surface features on asteroids and Mars. Bertacco is quick to note that the preliminary version of the online game features problems that are easily solved by today’s satisfiability algorithms. Her team’s goal is to expand the proof of concept into a multiplayer game in which many participants work on subsections of a large puzzle. The team is looking at examples of massive multiplayer online games like World of Warcraft, where many players work together to solve large problems. A multiplayer version is the only way humans will be able to tackle the large problems encountered in EDA. “We’re talking about tens of thousands of buttons,” says Bertacco, “and that’s just not feasible for an individual.”

http://spectrum.ieee.org/semiconductors/design/crowdsourcing-the-complexities-of-electronic 8/6/2009

Summary The article is about how humans can help electronic design automation and how many participants can work together to solve large problems.

Description An interesting read and an example of how the complexities of electronic design automation can be crowdsourced.

Tags: , Cloudworker, Cloudworking, Crowdsourcing, Electronic Design Automation, Games, Venkatesh Rao

Events

Crowdsourcing the Complexities of Electronic Design Automation

Comments

Crowdsourcing.org

Categories

Content

Crowdsourcing.org, an initiative by massolution®

Events

Related Content

Crowdsourcing the Complexities of Electronic Design Automation

Comments

Crowdsourcing.org

Categories

Content

Crowdsourcing.org, an initiative by massolution®