Create an Account
username: password:
 
  MemeStreams Logo

MemeStreams Discussion

search


This page contains all of the posts and discussion on MemeStreams referencing the following web page: Distributed Hardware Evolution. You can find discussions on MemeStreams as you surf the web, even if you aren't a MemeStreams member, using the Threads Bookmarklet.

Distributed Hardware Evolution
by Decius at 11:34 am EDT, Jul 30, 2003

] Evolving Self-Diagnosing Hardware was first attempted by
] the author for some toy circuits in the hope it would be
] possible. The toy circuits attempted where a two bit
] multiplier and a one bit adder. After hundreds of
] thousands of generations, circuits evolved performing
] full diagnosis using about half the overhead the
] conventional solution would have required. For example
] when using two-input logic-gate technology, a two-bit
] multiplier can be implemented using 7 gates. Adding an
] extra copy, and 7 more gates for comparing 4 outputs, we
] have an overhead of 14 gates for the conventional voting
] system BIST solution. After four million generations the
] GA found a circuit (diagram) with the same behaviour
] using only 9 extra gates. It is hard to work out exactly
] what operating principles underlie its operation but it
] looks like it tends to use more XOR gates which always
] propagate a bit flip in one of their inputs, and also
] exploits design diversity to compare multiple sections of
] the circuit simultaneously.

I'm going to have to look at this in detail tonight.

I'm a little sceptical. Its not "hard to work out exactly what operating principles underlie" a 9 gate circuit. "Exploits design diversity" sounds like something a politician would say. I'm fairly certain that karnaugh maps produce solutions that are proveably optimised for simple cases like this. If he got results from this technique he probably started with an improperly designed circuit.

This is not to say that evolving hardware isn't interesting. It just seems like something isn't right with this example. A little math will tell me, and I'll post an update later.


 
RE: Distributed Hardware Evolution
by lclough at 8:31 am EDT, Jul 31, 2003

Decius wrote:
] ] Evolving Self-Diagnosing Hardware was first attempted by
] ] the author for some toy circuits in the hope it would be
] ] possible. The toy circuits attempted where a two bit
] ] multiplier and a one bit adder. After hundreds of
] ] thousands of generations, circuits evolved performing
] ] full diagnosis using about half the overhead the
] ] conventional solution would have required. For example
] ] when using two-input logic-gate technology, a two-bit
] ] multiplier can be implemented using 7 gates. Adding an
] ] extra copy, and 7 more gates for comparing 4 outputs, we
] ] have an overhead of 14 gates for the conventional voting
] ] system BIST solution. After four million generations the
] ] GA found a circuit (diagram) with the same behaviour
] ] using only 9 extra gates. It is hard to work out exactly
] ] what operating principles underlie its operation but it
] ] looks like it tends to use more XOR gates which always
] ] propagate a bit flip in one of their inputs, and also
] ] exploits design diversity to compare multiple sections of
] ] the circuit simultaneously.
]
] I'm going to have to look at this in detail tonight.
]
] I'm a little sceptical. Its not "hard to work out exactly what
] operating principles underlie" a 9 gate circuit. "Exploits
] design diversity" sounds like something a politician would
] say. I'm fairly certain that karnaugh maps produce solutions
] that are proveably optimised for simple cases like this. If he
] got results from this technique he probably started with an
] improperly designed circuit.
]
] This is not to say that evolving hardware isn't interesting.
] It just seems like something isn't right with this example. A
] little math will tell me, and I'll post an update later.

Appears to be derived from Garvie's undergraduate thesis of 2001 and ties into other ongoing research at the Centre for Computational Neuroscience and Robotics. Anyone have insight as to the academic reputation of this group?


  
RE: Distributed Hardware Evolution
by Decius at 9:17 am EDT, Jul 31, 2003

lclough wrote:
] ] This is not to say that evolving hardware isn't interesting.
]
] ] It just seems like something isn't right with this example.
] A
] ] little math will tell me, and I'll post an update later.
]
] Appears to be derived from Garvie's undergraduate thesis of
] 2001 and ties into other ongoing research at the Centre for
] Computational Neuroscience and Robotics. Anyone have insight
] as to the academic reputation of this group?

Sounds like the kind of group that would know what they are talking about. If I'm missing something, however, I'll be suprised. I'm thinking that the explanation might be that those not xors might add up to the same transistor count as the nand gates he'd have been using in the original circuit. Unfortunately, I haven't had time to dig into this, and as I'm out of town this weekend it will probably be next week. I'm intrigued though, so I will look at it. If it turns out that he is right, that karnaugh maps don't produce optimal solutions, then this leads to the possibility that there might be a different way to do circuit optimisation. (I'm not talking about evolution, either... I mean a different procedural method...)


 
 
Powered By Industrial Memetics