ECE: Electrical & Computer Engineering
ECE News

Software/design automation

PROACTIVE

Visit the PROACTIVE research team website.

Simulated ants get to the hard-to-reach corner states

Diagram

One of the hardest problems in validating designs is getting the system to reach all the possible states it will experience during use. Michael Hsiao’s team has developed a new semi-formal validation technique that gets to those corner cases by drawing inspiration from nature. The Ant-Colony-Optimization-based state justification is based on how a swarm of ants searches for the best pathway to and from a food source. An individual ant uses its own senses to search for the best route, but it also lays down a pheromone track to lead other ants along a good route when found. As the swarm continues to search, the best route grows thick with pheromone tracks, while the tracks along poorer routes evaporate over time. Eventually, the pheromone-guided ants follow only the best path.

The algorithm simulates this same behavior with a swarm of simulated ants. The amount of pheromone left by the ants is directly proportional to the quality of the search. In addition, the intelligence based on the collective behavior is capable of avoiding critical dead-end states as well as fast convergence to the target state. Other researchers have proposed algorithms using random input or a genetic algorithm, but Hsiao’s team tested their ant-colony-optimization-based algorithm over a variety of state justification benchmarks, and found it faster in almost every case. “For many circuits, our technique is very effective in reaching hard-to-reach states where previous methods either fail or require more time,” Hsiao said.