Question for folks here who've worked on these 1 Billion+ transistor chips. How relevant is stuff like K-Maps in your day-to-day work? Is this stuff done by tools like Mentor-Graphics and Synopsis or do folks still lay this out by hand?
Karnaugh map
11–20 of 28 posts
Re: Karnaugh map
#12I remember it being quite a revelation as to how discrete digital circuits can be optimised Our Uni class execise revolved around designing a drink vending machine operation with a minimum number of logic gates.
Re: Karnaugh map
#13I remember it being quite a revelation as to how discrete digital circuits can be optimised Our Uni class execise revolved around designing a drink vending machine operation with a minimum number of logic gates.
Yeah, I have a similar recollection of lectures at college 30 years ago, and what seemed to be a hugely complex system being reduced drastically in complexity by the realisations contained within the maps. It was obviously a contrived situation that the lecturer had thought of, but there were many 'lightbulb' moments across the room in that hour.
Re: Karnaugh map
#14Question for folks here who've worked on these 1 Billion+ transistor chips. How relevant is stuff like K-Maps in your day-to-day work? Is this stuff done by tools like Mentor-Graphics and Synopsis or do folks still lay this out by hand?
It depends on what you're doing. Certainly for standard design you won't be looking at Karnaugh maps. You trust the implementation tool to deal with the logic minimisation for you.
In certain cases say a piece of logic on the critical path that's preventing your design clock as fast as you want or something complex that you know requires lots of effort to meet your ppa (power, performance, area) targets, say an ALU or part of an FP unit, you'll be doing more manual optimisation. However even then you're probably not using a Karnaugh map, instead using more sophisticated techniques and then using specialised programs to do these for you (Espresso being the classic example https://en.m.wikipedia.org/wiki/Espresso_heuristic_logic_min...).
There's also things that simple logic minimisation doesn't take into account like fan out (how many things you have hanging off a particular output) and wire distance (a significant proportion of the clock cycle can be taken up in waiting for signals to propagate if the logic is spread across the chip). A hand crafted piece of logic is likely to use a mix of 'pure logic' type optimization techniques (that are simply trying to minimise logical operations) and the engineer using their judgment to work out what arrangement of minimised functions leads to the best implementation result.
Re: Karnaugh map
#15Karnaugh maps are often made out as something special, but it's nothing more than a graphical brute-force method. Thus, useful for pen-and-paper up to 5-6 bit logic functions but no better than exhaustive testing for a computer. There seems to be little emphasis on the "why" in Computer Architecture courses.
Re: Karnaugh map
#16Thanks! I remember learning this in introductory circuit design 15 years ago, but forgot about it since. I actually needed it a few weeks ago, when I was trying to simplify a complex boolean expression in my C code :\
Quine–McCluskey algorithm might be of help to you.
ahhh memories...
Re: Karnaugh map
#17Learned those in undergrad .. was in Chapter 1 of our textbook .. Computer System Architecture, Morris Mano. Have used it twice with great results in my career.
Came here to say exactly this, Moris Mano is a very well written book. The subject was "Logic Design". Though I now don't recall what it was for, Karnaugh Map was one of my favourite pen and paper exercises. Fond memories indeed
Re: Karnaugh map
#18Learned those in undergrad .. was in Chapter 1 of our textbook .. Computer System Architecture, Morris Mano. Have used it twice with great results in my career.
Came here to say exactly this, Moris Mano is a very well written book. The subject was "Logic Design". Though I now don't recall what it was for, Karnaugh Map was one of my favourite pen and paper exercises. Fond memories indeed
I think it was supposed to minimize the number and kind of logic gates that would be required to build function.
Re: Karnaugh map
#19Re: Karnaugh map
#20Oh I remember this form my Digital Electronics course but I have never used them since then Because I haven't used actual pure combination logic since that course either.