Revisiting Kernighan-Lin Fiduccia-Mattheyses algorithm

KLFM (aka Kernighan-Lin Fiduccia-Mattheyses) is a well known graph bipartitioning algorithm in electronics design automation, genomics, logistic automation (packing), other key industrial applications. KLFM as we know it of today, was first published back in 1989 in “A Linear-Time Heuristic for Improving Network Partitions” paper [pdf]. That work, and later  research “Fast Hypergraph Partition” [pdf] was either based on the assumption or converted the network hyper graph (each hyperedge often connecting more than two nodes) into a simplified graph with simple edges (connecting only two nodes). Surprisingly, we were not able to find a simple KLFM open source implementation, so we dared to spend few evenings and developed an opensourced one to contribute to the community. Continue reading

Justification of Tcl, PHP and C++ use in Electronics Design

Years ago, open source visionary Richard Stallman started a comp.lang.tcl theme with “Why you should not use Tcl” title. Having implemented large Tcl projects with tens of thousands of lines of Tcl source code, we should partially agree with another quote from Stallmans address “Tcl is ok for writing small programs, but when you push it beyond that, it becomes insufficient“.  Small Tcl programs are extremely effective.  We previosuly twitted on a scripting language comparison and analysis why Tcl, while being a healthy and live, became a niche applications language. Let’s paractically explore by example, where Tcl, PHP (or Perl, Python, Ruby) and C++ fit in Electronics Design Automation software development cicle. Continue reading

EDA custom language parsing with Lex and Yacc

EDA early days was in mid 1970-s, when the first commercial place and route tools were developed. Gerber ASCII format was introduced for machine plotting and exchanging PCB information. Later semiconductor industry employed specialized text languages for ASIC design exchange, with human readable formats such as LEF, DEF and so on. With number of transistors on a chip exceeding few billions on a typical nowadays SoC, and size of the data exchange files becoming enormously large, it is critically important to use high performance language parsing technology.

Please recall Backus-Naur Form, most widely used notation technique for context-free grammar. BNF language syntax description provides a set of deviation rules, as example of DEF parser. Lex and Yacc allow using similar clear and understandable concept:

ndspecs: ndspec | ndspecs ndspec
        ;

ndspec: layer
        | via
        | viarule
        | spacing
        ;

word_via: WORD
        | VIA
        | LAYER
        | WIDTH
        ;

specword: word_via
        {
                spec_stack_add($1.string);
        }
        ;

In 1975, Mike Lesk and Eric Shmidt introduced complementary lexical analyzer generator Lex and parser generator Yacc for language parsing,that allowed developers to create very efficient C parsers. Modern GNU development tools share the same concept, with Flex as a GNU alternative for Lex and Bison being equivalent of Yacc.

We’d like to demonstrate creating Lex/Yacc parser in this walk-trough. Lex and Yacc description is beautiful and simple,  very much alike BNF, while generated C parser is blazing fast and does not require lots of RAM/CPU resources. Continue reading

MCU board schematic

Publishing schematic and board layout files (v18 – SMD 1-layer version, v17 – trough hole that actually went into last production batch) on source forge.

v18-schematic 17-еуые

Board features following components:

Singal line protection circuitry. It is needed to protect MCU from very strong automotive induced voltage spikes. Opto-coupler is used

optoinput

DC-DC regulated voltage stepdown supply with resettable fuse. Device can work on both USB (programming, logic analyzer, Parking Assistant frontend mode) and standalone (intelligent parking assistant) mode. Impulse regulator can be ultra-affordable 33063 or 34063 produced by virtually any semiconductor manufacturer (we used OnSemi).

dcdc

USB and external power self-sense socket (18F4550 datasheet module is impractical):

selfsense

USB Parktronic Firmware

From 2008 to 2012, we have shipped Microchip PIC 18F2550/4550 based USB parktronic device (and related projects) to clients in more than 20 countries. With number of customer support requests declined, we feel that it is right to retire this project and make it part of opensource. All the source code of USB Parktronic Firmware have been published on sourceforge, so you are free to change firmware in a way of your liking and produce those devices for your own need. We thank the customer base for continued support of this project.

Logic Analyzer

bitscopeIn a previous blog post, we’ve discussed USB microcontroller device that hooked up to a generic automotive parking radar to function as a safety device for a plastic fab robot. In order to connect to internal data bus of a 3-rd party device (and we have explored quite a few of them), a firmware on a pretty spacious 18F4550 Microchip controller also had Logic Analyzer functionality, which is capable of capturing 2-line (one can add more lines by adding digital inputs the original schematic) switching signals of up 1MHz working frequency. We created custom Qt C++ application for it, that we are willing to share for those who need to reverse engineer custom digital devices and run their own custom graphical data analyzis. Source code for your reference is published on Sourceforge.

Custom ASIC blocks design

design

 

Implementing a digital ASIC block requires understanding of dataflow and internal structure. General objectives are

  • minimize length of wiring required to connect all nets to external pins on the block boundary
  • minimize signal propagation delay, meet timing constraints
  • insert buffer and size gates to make sure block can operate on desired working frequency and consumes less power
  • by running vector logic simulation, verify thermal dissipation
  • in some cases try reducing block size and implement block in various aspect ratios
  • prepare documentation, technical papers and datasheet if block distributed in a form of hard IP

We have the experience doing full chip design (a customer asked to implement OpenSparc II based 90nm design from RTL to GDS), although our primary skillset is custom digital blocks layout using industry standard tools (Synopsys ICC, Cadence Encounter, and we have some legacy lower node tools at hand that allow us completing on medium complexity digital blocks).

it is easier to do block planning by looking into original RTL code, netlist heirarchy and understand logic structure. In some cases we advise recoding parts of RTL or tune sythnesis parameters / back annotate from P&R stage and re-synthesize the particular block, altough modern synthesis (Design Compiler) and P&R (Encounter, ICC) tools have gathered lots of designer heuristics over the years, interoperate well and generally produce acceptable results for ASICs.

Still placement and routing may use designer help in a form of floorplan as soft / hard blocks (modules, keep ins or keep outs – terminology vary), blocks relations, routing blockages. Designer may want to interfere with detaield placement to generate datapath module for a bus with a custom script or 3-rd party tool, it can also require some try-and-probe design iterations trying to downsize gates, reduce bounding box of a block, etc and verify block timing each time.

We can add extra value to custom design by developing point EDA tools / scripts for a particular block that is aware of it’s internal structure and allow achieving dramatic layout quality optimization, nearly hand-crafted layout quality. Those tools can be very helpful when migrating ASIC block to higher technology node (from 90nm to 65nm, for example) or different technology (UMC <-> XFAB <-> TSMC <-> GF).

Opensource Qt/C++ GUI

parkassNovorado posseses strong Graphic User Interface development skills with a lot of legacy Tubro Vision, Borland OWL, MFC, X-Window, Motif projects. Since Trolltech emerged with Qt framework in 1994, we have become strong advocates of the Trolls, and used Qt in complex GUI applications for medical, semiconductor users. For demonstration purposes, we would like to comment on a demonstration open source project that was placed on SourceForge some time ago.  Continue reading