Home

project. The report

1. os Geo 3 2 1 A and B are isomorphic graphs a 5 ig aria 6 fe begets aa ch he Saw ee kG 8 bb ha ae AOR Ae I S A AS ee Bice ee ew eS 11 Pay are a oe QUE RITI A ee eae Be ee eii 16 I ee asas 17 3 5 Luellau s algorithm cannot find any supercircuit for this circuit 21 DO Ar Verter creuit es vens ted a a ae ee GA at ia 22 TL 31 J r de ei 31 5 3 Example of a part of graph ee 33 vau ms 35 5 5 The removal of transitive edges a 36 5 6 A is a subcircuit of B and B is a subcircuit of C but A is not a subcircuit of C 39 ID ID EI 46 7 1 A part of graph drawn from a real database containing ten circuits 50 O WEG Gee Boe ROM poe eee a S 54 7 3 A histogram showing the efficiency of the search tool 2 56 jh te da ad fra 57 ii 59 ur 50 7 7 The part of graph for the entire test corpus a a a 63 PCT 66 8 2 An improved version of the part of graph shown in Figurc I with two dummy circuits 66 A gs S D Sa i 68 ix Chapter 1 Introduction 1 1 Rationale for the project The circuit repository which is being built by the Department will hold a large number of electronic circuits of interest to those learning about circuit design Initially many of these circuits will be analogue circuits they will not be composed of digital logic gates but more primitive components such as transistors and capacitors In order to provide th
2. Circuit_Manager circuit location return true return circuit Test_Connectedness o D 30 libcrdb src serialisable signature cc include serialisable_signature h using namespace std Serialisable_Signature Serialisable_Signature unsigned n Serialisable number of types n assert number of types gt 0 counter new unsigned number of types for unsigned i 0 i lt number of types i counter i 0 void Serialisable_Signature Make_Copy Project Source Code 30 40 60 70 80 90 libcrdb src serialisable signature cc 166 const Serialisable Signature amp s unsigned x counter copy 0 if number of types gt 0 counter copy counter number_of_types s number_of_types if number_of_types gt 0 counter new unsigned s number of types for unsigned i 0 i lt number of types i counter i s counter i if counter_copy 0 delete counter_copy Serialisable Signature Serialisable Signature if number of types 0 delete counter void Serialisable Signature Debug void const ifdef DEBUG cout lt lt u for unsigned i 0 i lt number_of_types i cout lt lt counter i lt lt o cout lt lt endif void Serialisable_Signature Register_Component uns
3. add external nodes to external list while node_number Get_Net_Vertex_Number amp line gt 0 subcircuit gt external_nodes i node_number i 440 void Spice_Interpreter Read_Subcircuit_Device_Vertex char line Spice_Node_Map amp parent_nodes Get the subcircuit name Read the last word in the line This identifies the subcircuit char last word rindex line assert last word NULL 450 last word if spice subcircuits count last word 0 Get the subcircuit pointer Spice Subcircuit subcircuit spice subcircuits last word assert 0 460 Spice Node Map subcircuit nodes subcircuit node 0 must be the same as parent node 0 subcircuit nodes 0 Get Spice Node 0 parent nodes For each pin map the node in the parent circuit that the pin is connected to to the node in the subcircuit that the pin is connected to Project Source Code libcrdb src spice_interpreter cc 174 for Pin pin 0 pin lt subcircuit gt external nodes size pin 470 1 Spice Node Number ext node num Get Net Vertex Number amp line Spice Node Number int node num subcircuit gt external nodes pin Net_Vertex ext_net Get_Spice_Node ext_node_num parent_nodes assert subcircuit nodes count int node num 0 subcircuit nodes int n
4. gt weight 0 begin estr begin gt weight and 0 begin we are that gt dev_partition D that net partition 230 240 250 260 270 280 290 300 145 libcrdb src ohlrich circuit cc mri match count mc match records return match count void Ohlrich Circuit Initial Labelling void Device_Vertex_List_Iter dli Net_Vertex_List_Iter nli debug Initial Labellinguforu s An c ircuit name dev partition net partition Unlike the reference code special for dli master device list begin dli master device list end dli Device Vertex dev dli dev gt weight positive randomi int dev gt type for dev_partition estr clear clear E Os dev gt weight push front dev debug Device 4suwasyinitiallyylabelledqwith d n nli master net list begin nli master net list end nli Net Vertex net nli net gt weight positive random2 net gt connections net partition dev gt name net gt number bool Ohlrich Circuit net weight debug Net 4d was initially jlabelled with 4dNn net weight c str dev weight Relabeller Partition amp p Change
5. Project Source Code 620 630 640 660 670 680 690 libcrdb src ohlrich circuit cc 150 void Ohlrich Circuit ifdef DEBUG Partition iterator pi Vertex List Iter vli Print Partition const char 1 for pi p begin pi p end pi Vertex_List region pi second debug si weightu sd 1 pi first for vli region begin vli region end vli i Vertex vertex vli if vertex gt is net debug uu d s Partition amp p Net_Vertex vertex gt number vertex gt border jo if vertex gt assigned debug gt d Net_Vertex vertex gt matches gt number else debug uu s s Device Vertex vertex gt name c str vertex gt border jo if vertex gt assigned debug gt s Device_Vertex vertex gt matches gt name c str debug Nn endif Every weight that is remove_from but not in reference is removed This is like the set difference operation X Y void Ohlrich_Circuit Remove_Diff_Nodes Partition amp remove_from Partition amp reference Partition iterator p_ref_iter p_remove_iter Print Partition remove from remove from Print Partition reference reference p remove iter re
6. Device_Vertex dev cli gt device Pin pin cli gt device_pin 90 net gt weight Get_Luellau_Weight dev gt type pin It still works if the next line is uncommented proving that the reference circuit may be entirely closed and it makes no difference net gt open amp reference circuit debug Nety duweighty d n net number net gt weight 100 net list by weight net gt weight push front net Project Source Code libcrdb src luellau circuit cc 130 bool Luellau Circuit Get Starting Point void How many unique edges does each net vertex have 110 Find the closed net vertex with the most unique edges if any This is the best starting point if it exists bool best net vertex found false int best net vertex unique edges 0 Net Vertex x best net vertex OL Net Vertex List Iter nli for nli master net list begin nli master net list end nli 120 1 Net Vertex net nli Edge Map es 3 net open f net gt assigned continue bro cd Pa 130 Get Unique Edges net es int unique edges es size debug 4d unique edges onynet d Nn unique edges net gt number if unique edges gt 0 amp amp best net vertex found best net vertex unique edges LESSTHAN unique edges 140 debug Best n
7. sub Load_Circuit_Directly return 0 120 return circuit gt Is Subcircuit sub circuit mrl assume all vertices are open only find one match Sort by size void Serialisable Circuit Record Debug void const 130 ifdef DEBUG Project Source Code 140 160 170 180 190 200 libcrdb src serialisable circuit record cc 164 cout lt lt nDebugyoutputyfory lt lt circuit name lt lt Nn lt lt uufileylocationy lt lt location lt lt NnuuSignature Vnuuuu signature Debug cout lt lt Nn if circuit 0 circuit gt Debug endif bool Serialisable_Circuit_Record Write std ofstream amp out const bool rc true string type_str rc rc amp amp Write Magic out rc rc amp amp circuit name Write out rc rc amp amp location Write out rc rc amp amp signature Write out switch type case SPECIAL_EMPTY type_str e break case SPECIAL_UNIVERSAL type_str u break case PART_CLOSED type_str p break default type_str a break Jj rc rc amp amp Serialisable String type str Write out if Is Special assert circuit OL rc rc amp amp circuit gt Write out return rc bool Serialisable_Circuit_Record Read std ifstream amp in Serialisable_String type_str
8. 330 1 change item vertex v change list gt push front change item p clear p new_p 340 return progress void Ohlrich_Circuit Relabel_Non_Border_Vertex bool amp open_flag bool amp progress int amp sum Vertex v Device_Vertex_Connection_Map_Iter cmi Net_Vertex_Connection_List_Iter cli sum v gt weight 350 open_flag false progress false if v is_net Net Vertex x vertex Net Vertex v for cli vertex gt connections begin cli vertex gt connections end cli Device_Vertex dev cli gt device 360 Pin dev_pin cli gt device pin if open_flag dev gt border break The reference implementation does something different for nets than for devs and I cannot understand why It looks like a bug 370 graph c line 1020 1123 sum dev gt weight Get_Ohlrich_Weight dev gt type dev_pin else Device_Vertex vertex Device_Vertex v for cmi vertex gt connections begin cmi vertex gt connections end cmi 380 Net Vertex net cmi second Pin dev pin cmi first Project Source Code 147 libcrdb src ohlrich circuit cc if open flag net gt border break Note the different behaviour for devs vs nets sum net gt weight Get_Ohlrich_Weight v
9. P yp printf t tSuby su sumatches toysupery syss n type_str match_item_ptr gt subcircuit_item type_str match_item_ptr gt supercircuit_item match_item_ptr match_item_ptr gt next printf An match info ptr match info ptr gt next tf Nu js Project Source Code include interface h result_ptr result_ptr gt next matches if matches 0 printf ThereyaregnoL4ssuofu s n n _ search_type_str file_name 170 else printf du ssuofu s uwere_found NnNn matches search_type_str file name rc CR Free Result List amp result list if rc CR_OK printf CR_Free_Result_Listufailed y sYn CR_Get_Error_String rc 180 exit 1 D 4 include interface h interface h Provides a C API to the C database functions This is only needed if the database functions are needed from a C program if your program is C then you can make use of the database directly by including libcrb include database h 10 ifndef CR DB INTERFACE H define CR DB INTERFACE H ifdef cplusplus define CR EXT extern C else define CR EXT endif 20 ifndef BOOL typedef enum FALSE 0 TRUE BOOL Hendif typedef enum CR_OK CR_FILE_NOT_FOUND CR_OUT_OF_MEMORY CR_NO_DATABASE CR INVALID HANDLE CR DATABASE HAS ALREADY BEEN BUILT CR DATABASE ALREADY EXISTS CR FILE FORMAT
10. if circuit OL delete circuit Project Source Code 163 libcrdb src serialisable circuit record cc Serialisable_Circuit_Record Serialisable Circuit Record const Serialisable Circuit Record amp m circuit OL location m location 60 type m type signature m signature circuit name m circuit name Serialisable_Circuit_Record amp Serialisable_Circuit_Record operator const Serialisable_Circuit_Record amp m circuit OL 70 location m location type m type signature m signature circuit_name m circuit_name return this Returns the number of times that sub is a subcircuit of this 80 int Serialisable_Circuit_Record Is_Subcircuit Serialisable_Circuit_Record amp sub Match Record List amp mrl bool assume all vertices are open bool only find one match bool sort by size mrl clear switch type 1 90 case SPECIAL_UNIVERSAL return UINT_MAX well infinity really case SPECIAL_EMPTY return 0 default switch sub type 1 case SPECIAL_UNIVERSAL return 0 case SPECIAL_EMPTY 100 return UINT_MAX default fall through break if amp sub this It s an auto comparison return 1 else 110 if it s not a signature subset it can t be a subcircuit of this if Is Signature Subset sub Load_Circuit_Directly
11. include map include lt assert h gt namespace std class Database public Serialisable public public types enum Search Type SEARCH_FOR_SUBCIRCUIT D Project Source Code 20 30 40 60 70 80 90 101 libcrdb include database h SEARCH FOR SUPERCIRCUIT SEARCH FOR EQUIVALENT struct Search Flags Search_Type search_type bool dont_assume_open bool only_find_first_match bool sort_by_match_size ys struct Search_Result_Record Match_Record_List match_record_list Serialisable_Circuit_Record circuit ys struct Search_Result_List Constant_Time_List lt Search_Result_Record gt constructor destructor Database virtual Database public procedures void Add_Circuit Serialisable_Circuit_Record c void Build void void Search Serialisable_Circuit_Record amp for this Search Flags sf Search Result List amp results virtual bool Write std ofstream amp out const virtual bool Read std ifstream amp in virtual void Debug void private copy assign not allowed Database const Database amp assert 0 Database amp operator const Database amp assert 0 private types struct Circuit List Constant Time List Serialisable Circuit Record gt typedef Circuit List iterator SCRI struct Search Result Map multimap lt double Search Result Record
12. 520 comparison conflict true break if nv assigned amp amp nv matches nvp nvp matches nv nvp gt assigned net is already assigned to something else debug uuComparisonuconflict unet passigned Nn 530 comparison conflict true break debug uuWouldulikeutoumatchunetsu duandu dNn nvp gt number nv gt number A Can we match those net vertices Beware that the nvp vertex may be open if nvp gt open 540 if nv gt weight nvp gt weight 0 debug uu Comparison conflict weights are wrong 4duvsu4d even though openAn nvp gt weight nv gt weight comparison conflict true break else 550 if nv gt weight nvp gt weight debug Comparison conflict weights are wrong hduvsusd n nvp gt weight nv gt weight comparison_conflict true break 560 match them nv gt assigned nvp gt assigned true nvp gt matches nv nv gt matches nvp match eip and ei ei gt assigned eip gt assigned true eip gt matches ei Project Source Code libcrdb src luellau circuit cc 136 ei gt matches eip 570 store nvp in net stack net stack push front nvp debug uuMatched uaddedu dutoustack Nn nvp gt number no progress
13. Deterministic_Matching_Result rc if that gt starting net vertex OL Starting at a device vertex Device_Vertex_List device_list_by_weight that gt starting_device_vertex gt weight Device_Vertex_List iterator dvi for dvi corresponds begin dvi corresponds end amp amp rc OK dvi Device_Vertex dv_match dvi if dv_match gt assigned continue corresponds ae UE s j Project Source Code Nondeterministic Matching void COMPARISON CONFLICT 133 libcrdb src luellau circuit cc debug Device Vertex Matching u Weuwilluguessuthatu sucorrespondsutoy4s Nn 340 that gt starting device vertex gt name c str dv_match name c_str net stack clear device stack clear put it on the device vertex stack device stack push front that gt starting device vertex mark the correspondence 350 assert that gt starting device vertex gt assigned assert dv match gt assigned that gt starting device vertex gt matches dv match that gt starting device vertex gt assigned true dv match gt matches that gt starting device vertex dv match gt assigned true rc Deterministic Matching debug Device Vertex Matching u Xsucorrespondsutou ds yu 360
14. Vertex List amp region pi second assert region empty 1100 if graph partition count weight 0 debug Failed TEC No partitionjof weight Ad Nn weight return false Vertex_List amp super_region graph_partition weight if super_region size lt region size 1110 debug Failed TEC yPartitionjofuweightu d Lisytooysmall n weight return false return true void Ohlrich_Circuit Verify_Image_Core Partition amp subgraph_partition_copy 1120 Partition amp graph_partition_copy Change List change list bool amp equiv class check failed bool amp progress progress Relabeller subgraph partition copy change list hlrich Circuit Relabel Neighbours 0f Safe Nodes true debug uucheck youtputuhasu dyregions uprogu d Nn subgraph partition copy size progress 1130 progress Relabeller graph partition copy change list hlrich Circuit Relabel Neighbours 0f Safe Nodes true debug uucheck youtputuhasu dyregions uprogu d Nn graph partition copy size progress If some partition in subgraph partition copy with weight X is bigger than the partition with weight X in graph partition copy then the equivalence is broken and we must stop Looks like the assumption made 1140 when this procedure was called was false if Test Equivalence Classes subgraph partiti
15. amp amp rc rc dli gt name Write out rc rc amp amp Type To String dli gt type Write out rc rc amp amp Write Integer out dvcm size Device Vertex Connection Map const iterator dvcmi for dvcmi dvcm begin dvcmi dvcm end dvcmi 680 1 pin number rc rc amp amp Write Integer out dvcmi first net number assert nets count dvcmi second 1 rc rc amp amp Write Integer out nets dvcmi second net information SPICE number and open status rc rc amp amp Write Integer out 690 dvcmi second gt number dvcmi second gt open IS OPEN 0 return false if rc return rc Project Source Code 177 libcrdb src spice_interpreter cc 700 bool Spice_Interpreter Read std ifstream amp in map lt int Net Vertex x gt nets unsigned i num devices bool rc true assert master net list empty assert master device list empty assert master connection list empty 710 Serialisable String circuit name ser rc rc amp amp circuit name ser Read in circuit name circuit name ser unserialise device list rc rc amp amp Read Integer in num devices for i 0 i num devices i Device Vertex dev new Device Vertex 720
16. dli gt matches lt lt Nn A Device Vertex Connection Map amp dvcm dli gt connections Device Vertex Connection Map const iterator dvcmi for dvcmi dvcm begin dvcmi dvcm end dvcmi cout lt lt PIN lt lt dvcmi first lt lt y lt lt int dvcmi second lt lt dvcmi second gt open qOPEN n Nn cout lt lt DEVICELENDL lt lt dli gt name lt lt An cout lt lt CIRCUITDATA END lt lt circuit name lt lt An Serialisable_String Spice_Interpreter Type_To_String Type t const const char s switch t case DIODE g pee break case RESISTOR SRN 3 break case CAPACITOR g UON break case INDUCTOR gu de break case NPN s NP break case PNP s PN break case NMOS s NM break case PMOS s PM break case NJFET s NJ break case PJFET s PJ break case UNKNOWN s U break Project Source Code 860 870 880 890 900 910 920 179 libcrdb src spice interpreter cc return Serialisable String s Spice_Interpreter Type Spice_Interpreter if Type_To_String DIODE compare s 0 return DIODE else if Type_To_String RESISTOR compare 6 0 return RESISTOR else if Type_To_String CAPACITOR compare s 0 return CAPACITOR else
17. gt starting net vertex gt assigned true nv match gt matches that gt starting net vertex nv match gt assigned true Project Source Code 420 430 440 450 460 ATO 480 490 libcrdb src luellau circuit cc 134 rc Deterministic Matching debug Net Vertex Matching Xducorrespondsutou 4d y that gt starting_net_vertex gt number nv_match gt number switch rc case OK debug yes n break case NO UNIQUE EDGES cant true can t do it fall through case COMPARISON CONFLICT debug no n this gt Manipulate_Flags CLEAR_UNFINALISED that gt Manipulate_Flags CLEAR_UNFINALISED break f rc OK return cant IMPOSSIBLE FAIL this gt Manipulate_Flags FINALISE that gt Manipulate_Flags FINALISE return REPEAT Luellau_Circuit Deterministic_Matching_Result Luellau_Circuit Deterministic_Matching void bool comparison_conflict false int cycle 0 bool no_progress true do debug CYCLEL c n cycle A cycle while device_stack empty amp amp comparison conflict Device Vertex dvp device stack front device stack pop front assert dvp gt assigned Device Vertex dv dvp gt matches assert dv gt assigned debug DV Test
18. 130 1 debug XYZZYuOuufailveguivu2Nn return 0 Remove Diff Nodes this gt dev partition that gt dev partition point 8 if empty 140 break Print Partition Aythisy gt dev_partition this gt dev partition Print Partition A that gt Ldev_partition that gt dev partition Print Partition Ayjthis net partition this gt net partition Print Partition Ajthat 7 net partition that gt net partition 150 Now find the candidate vector and key node if that gt dev partition empty Project Source Code were WH were HY WH 160 170 180 190 200 210 220 libcrdb src ohlrich circuit cc 144 assert that gt dev partition assert that net partition empty Remove Diff Nodes this gt dev partition return 0 f this gt dev_partition empty O empty A device vertex will be the key node Find the smallest of all remaining partitions Find_Candidate_Vector this gt dev_partition candidate_vector assert that gt dev_partition count candidate_vector keynode Vertex that gt dev partition candidate vector assert keynode OL begin gt weight debug XYZZY jO device keynode name As Nn Device Vertex keynode gt name else Now we have a cand
19. 2 input NAND gate p34 c1 2 input NAND gate p12 c1 PZZZZZZZ 27277222472222277427272772 i a II DAMM a Pel EZZZZZZZIZZ22722221 TTA 27772777 122 a a ar E PI 2 input AND gate p18 c1 J Generic Standard NAND p 8 cl Prasu ss a aera 2 input NOR gate p14 c1 PEZZ7ZZZAZZZZZZIAZIZIZZZAZIZIZZIZZZZZZZA 3 input AND gate p26 cl EE TLLA zz pv P7777 2 input OR gate p20 c1 E ZZZ GITA ZIZIIITADITIZITA 22 ZZZZZARIZITITIFITITITTA 3 i nput AND gate p DENM 2 i np ut NOR gate p 36cl EZZZZAZHZULRZALLLLILLLLLIEA 4 L 0 5 10 15 20 25 30 35 40 45 50 Time Milliseconds Figure 7 4 A bar chart showing the time taken by the Search procedure to carry out two types of search for various circuits These timings are not necessarily typical of the ones that will be obtained using a different database containing other circuits They are highly dependent upon the size of the circuits and the number of circuits in the database However it is reasonable to suspect that the timings obtained here are indicative of the performance of the search tool in actual use since both the sizes and types of circuit used in testing are typical of those found in the Book Emulator How does circuit size affect performance The circuits used to produce the data for Figure are all quite small containing only 10 to 15 devices It is reasonable to question the performance of the search tool with circuits that are much larger Evaluating
20. A Graph Matching Search Algorithm for an Electronic Circuit Repository Jack Whitham 2003 2004 A report on a project submitted for the degree of MEng CSSE at the University of York This project report consists of 33911 words as counted by the Unix wc com mand after detex was run on the LaTeX source This count excludes the Appendices There are 70 pages in the main body of the report ii Abstract The Department of Computer Science at the University of York is creating a repository of electronic circuits The repository will assist students learning about the design of electronic circuits helping to explain why a circuit has the layout it does and how it performs its function One important feature of this repository will be a search tool allowing students to match circuits that they have drawn to those in the repository The tool must provide a means for exact or partial matching of a new circuit with those stored in the repository This project investigates some existing algorithms intended for general circuit comparison and proposes a new algorithm based on one of them which is designed to carry out the required type of search automatically The front cover image was produced by the author using the POVRay raytracer It is based upon circuit diagrams taken from the Book Emulator 3 and a daVinci 9 diagram of a test circuit repository ii lv Table of Contents 1 Introduction 1 1 Rationale for the projec
21. Serialisable Signature sig NUMBER OF TYPES for dli master device list begin dli master device list end dli const Device Vertex dv dli switch dv type 570 1 case INDUCTOR sig Register Component 0 break case DIODE sig Register Component 1 break case NPN sig Register Component 2 break case PNP sig Register Component 3 break case RESISTOR sig Register Component 4 580 break case CAPACITOR sig Register Component 5 break case NMOS sig Register Component 6 break case PMOS sig Register Component 7 break case NJFET sig Register Component 8 break case PJFET sig Register Component 9 590 break case UNKNOWN assert 0 break ifdef DEBUG cout lt lt circuitu lt lt circuit name lt lt has signature sig Debug cout lt lt An 600 endif return sig void Spice Interpreter Build Match Record Spice Interpreter that 1 Device_Vertex_List_Iter dli 610 Net_Vertex_List_lter nli Match_Record m for dli that gt master_device_list begin dli that gt master device list end dli assert dli assigned m device matches push front pair lt string string dli gt name dli gt matches gt name for nli that gt master net list begin 620 Project Sour
22. The set for Z is thus not a superset of the set for X which is g There are two solutions to this problem Firstly the problem can be eliminated entirely by the introduction of a rule stating that any closed vertex in a circuit C may not become open in any supercircuit of C But this rule is not practical because there is no intuitive reason why any user of the circuit repository software should have to mark vertices as open or closed in order to obtain matches Users will expect to be able to search for subcircuits of circuits they have drawn and they will not expect to get different matches according to whether vertices are marked as open or closed The second solution bypasses the problem by ignoring the open or closed status of vertices in the supercircuit and assuming they are all open So when the software tests to see if A is a subcircuit of B will compare the set of all net vertex types in B with the set of closed net vertex types in A 32 A Graph Matching Search Algorithm for an Electronic Circuit Repository In the example illustrated in Figure a program would take the set of net vertices for X to be g the only closed net vertex and the set for Y to be acefghij As the set for X is a subset of the set for Y the program would know that Y could be a supercircuit of X and would be able to carry out a more thorough test This second solution does not require the user to mark any vertices as open or closed It is also easy t
23. bool rc true rc rc amp amp Read Magic in rc rc amp amp circuit name Read in rc rc amp amp location Read in rc rc amp amp signature Read in rc rc amp amp type str Read in if type_str compare e 0 1 type SPECIAL_EMPTY else if type_str compare u 0 1 type SPECIAL_UNIVERSAL else if type_str compare p 0 1 type PART_CLOSED else if type_str compare a 0 t type ALL_OPEN else assert 0 Project Source Code 210 220 240 250 10 20 165 libcrdb src serialisable signature cc if Is_Special if circuit OL circuit new Circuit Manager rc rc amp amp circuit gt Read in return rc void Serialisable_Circuit_Record Load_Circuit_Directly void if Is_Special if circuit OL circuit new Circuit_Manager location bool Serialisable_Circuit_Record Is_Signature_Subset Serialisable_Circuit_Record amp sub const if sub type SPECIAL_EMPTY type SPECIAL_UNIVERSAL return true else if sub type SPECIAL_UNIVERSAL YP type SPECIAL_EMPTY return false else return signature Is Subset sub signature bool Serialisable_Circuit_Record Test_Connectedness string amp o if Is_Special
24. comp if best_device_vertex OL debug XYZZYuLuNoustartingupoint pavailableNn 200 starting net vertex OL starting device vertex OL return false if best device vertex unique edges 0 debug XYZZY LyCan tyuse this n Now this is something that Luellau s algorithm does not handle It means we not only have a non deterministic 210 choice of possible matches but we can t tell which one is right and which one is wrong We had better make it so that Deterministic Matching can return INCONCLUSIVE to force the choice of a different node or something debug XYZZY LU Willjuse device vertex 4 s n 220 best device vertex gt name c_str starting_net_vertex OL starting_device_vertex best_device_vertex return true Luellau_Circuit Match_Result 230 Luellau_Circuit Compare_To Luellau_Circuit kt Match_Record_List amp mrl that amp t match_records clear if prepared 240 Preparations true if that gt prepared that Preparations false this is the reference circuit the larger of the two that is the fragment being compared to it 250 debug Rewind n Clear all flags disregarding the finalised flags this Manipulate Flags CLEAR ALL that Manipulate Flags CLEAR ALL this edge record list clear that edge r
25. cr record gt next previous record cr record gt circuit name C String circuit Get Circuit Name cr record gt circuit file location C_String circuit Get Circuit Location previous record cr record j db record match record list end while j db record match record list begin Jo Match Record amp match record j CR Match List cr match new CR Match List CR Match Items x previous_items OL cr match gt next previous match previous match cr match copy device vertex matches for k match record device matches begin k match record device matches end k string subcircuit device k first string supercircuit device k second CR Match Items cr items new CR Match Items r b Search Result List iterator i j previous record OL egin db_record circuit cr_record cr_items gt subcircuit_item C_String subcircuit_device cr_items gt supercircuit item C_String supercircuit_device cr items gt type CR_DEVICE cr_items gt next previous_items previous_items cr_items copy net vertex matches i db_record new CR_Result_List for 1 match_record net_matches begin 1 match_record net_matches end 1 int subcircuit net 1 first int supercircuit net 1 second CR Ma
26. delete str is this correct static char C_String const string amp s char x str new char s length 1 460 strcpy str s c_str return str static char C_String int i char buffer 32 snprintf buffer 31 d i return C_String string buffer 470 static CR_Error_Code Translate_Exception const char ex if ex database_not_built return CR DATABASE HAS NOT BEEN BUILT else if ex database already built return CR_DATABASE_HAS_ALREADY_BEEN_BUILT 480 else if ex file access error return CR_FILE_NOT_FOUND else if ex file format error return CR_FILE_FORMAT_ERROR else return CR OTHER ERROR Project Source Code
27. e Feature 3 Search for fragments The database may contain circuit fragments which if present in a user circuit will be found by a search To find these fragments the CR Find procedure would be called with a search type of CR SEARCH FOR _SUBCIRCUIT The results list might then be screened to include only fragments that contained particular components so that a user could select a particular component and search for all the fragments that it was a part of This would make it possible for a user to indicate the part of the circuit that is of particular interest as has been illustrated in F igure 2 4 e Feature 4 Search for extensions The user provided circuit may be part of a larger database circuit that can be found by a search To do this the CR Find procedure would be called with a search type of CR SEARCH FOR_SUPERCIRCUIT since the fragments will be subcircuits of the user provided circuit These features may all be useful to a user Features 1 and 2 may be useful for checking the correctness of a circuit and perhaps for finding a circuit in the database when its name is not known Feature 4 is even more useful for identifying unknown circuits since the user can simply draw a small part of the circuit and then search for all circuits that contain that part Feature 4 is also useful for finding all the ways that a particular fragment of a circuit might be extended It can also be used to find all the circuits that have
28. iterator device definitions iter fd getline line buffer READ LENGTH circuit name if d good amp amp fd eof throw file access error line index line buffer Nn if line OL line 0 0 circuit_name string line_buffer It was initially possible to parse a circuit in one pass However this is not possible when a subcircuit X1 is used before it is defined Two passes are required now pass one while end fd getline line buffer READ LENGTH if fa good amp amp fd eof line line_buffer throw file_format_error Eat_Leading_Spaces amp line Project Source Code 169 libcrdb src spice_interpreter cc Directives start with comments start with switch line 0 1 case 0 case x comment or blank line ignore break 90 case Directive We only process the directives we understand if Directive Is line subckt Read_Subcircuit fd line else if Directive_Is line end end or ends end subcircuit end true 100 else if Directive_Is line model a device model Read_Model line break default A device definition wait for pass 2 device_definitions push_back string line break 110 pa
29. node map nn new_node new_node gt number nn Just for debugging 980 new_node gt open false new_node gt assigned false new node gt is net true new_node gt connections clear new_node gt matches OL master_net_list push_front new_node return node_map nn 990 Spice_Interpreter Spice_Node_Number Spice Interpreter Get Net Vertex Number char line if line NULL return 1 const char s Get Word line c str 1000 char x end Spice Node Number n n Spice_Node_Number strtol s amp end 10 if const char end s Project Source Code 181 src interface cc nothing read return 1 else 1010 return n D 33 src interface cc interface cc Provides a C API to the C database functions This is only needed if the database functions are needed from a C program if your program is C then you can make use of the database directly by including libcmsdb include database h XA kk X X X X X X 10 include lt string gt include lt fstream gt include lt iostream gt include database h include serialisable circuit record h include interface h include cr exceptions nh 20 using namespace std typedef struct CR Handle struct unsigned int magic Database x data CR Handle define ptr x _CR_Handle x define mag x CR Handle x
30. static const int PRIMES NUMBERPRIMES 1637 1627 1621 1619 1613 1609 1607 1601 1597 1583 1579 1571 1567 1559 1553 1549 1543 1531 1517 1511 1499 1493 1489 1487 1483 1481 1471 1453 1451 1447 1439 1433 1429 1427 1423 1409 1381 1373 1369 1367 1361 1327 1321 1319 1307 1301 1297 1291 1289 1283 1279 1277 1259 1249 1231 1229 1223 1217 1213 1201 1193 1187 1181 1163 1153 1151 1129 1123 1117 1109 1103 1097 1091 1087 1069 1063 1061 1051 1049 1039 1033 1021 1019 1013 1009 997 991 983 977 971 967 953 947 941 937 929 919 911 907 887 883 881 877 863 859 857 853 839 829 827 823 821 811 809 797 787 773 769 761 757 751 743 739 733 727 719 709 701 691 683 677 673 661 659 653 647 643 641 631 619 617 613 607 601 599 593 587 577 571 569 563 557 547 541 523 521 509 503 499 491 487 479 467 463 461 457 449 443 439 433 431 421 419 409 401 397 389 383 379 373 367 359 353 349 347 337 331 317 313 311 307 293 283 281 277 271 269 263 257 251 241 239 233 229 227 223 211 199 197 193 191 181 179 173 167 163 157 151 149 139 137 131 127 113 109 107 103 101 97 89 83 assert return PRIMES 79 73 71 67 61 59 53 47 43 41 37 531 29 23 19 17 end code from reference implementation C n gt 0 n amp amp n NUMBERPRIMES
31. toplevel_node_map end snmi 170 Net_Vertex net snmi second assert net gt connections empty net gt open true debug Madeynety dyopen n net gt number Finalise the types of certain devices transistors according 180 to the model information simultaneously sorting all the devices by type Device_Vertex_List_Iter eli for cli master device list begin cli master device list end cli Device_Vertex comp cli debug compunameL4sumodelu 4su 190 comp gt name c_str comp gt model c_str if comp gt model length gt 0 amp amp spice_models count comp gt model 1 amp amp comp gt type UNKNOWN The model field is filled in for this device use it to update the type comp gt type spice models comp gt model debug typeyisy d n comp gt type else 200 debug typeunotysetu 4dumodels n spice_models size Ensure that the type is not UNKNOWN it may be if the model isn t set correctly if comp gt type UNKNOWN cerr lt lt Circuit lt lt circuit name lt lt lt lt componenty lt lt comp gt name lt lt hasjan invalid model An throw file format error 210 Free memory used to store model and subcircuit data spice_subcir
32. true sum net gt weight 1030 Get Ohlrich Weight vertex gt type dev pin if relabel v weight positive sum return true There has been a change Progress was made 1040 else return false void Ohlrich_Circuit Backup void net_partition_backup net_partition dev_partition_backup dev_partition 1050 void Ohlrich_Circuit Restore void net_partition net_partition_backup dev_partition dev partition backup void Ohlrich_Circuit Reset_Flags Partition amp p Border_Flag_Operation f 1060 Partition iterator pi for pi p begin pi p end pi Vertex_List amp region pi second Vertex_List_Iter vi for vi region begin vi region end vi 1070 switch f case SET BORDER vi gt border true break case CLEAR_BORDER vi gt border false break Project Source Code libcrdb src ohlrich circuit cc 156 case COPY OPEN vi border vi gt open break default break 1080 vi assigned x vi gt safe false bool Ohlrich_Circuit Test_Equivalence_Classes Partition amp subgraph_partition Partition amp graph_partition 1090 Partition iterator pi for pi subgraph partition begin pi subgraph partition end pi int weight pi first
33. 0 i lt sz i 100 rc rc amp amp Read_Integer in x amp amp Read_Integer in y if rc map insert map end pair lt unsigned unsigned x y J return rc 10 D 29 libcrdb src serialisable circuit record cc include serialisable circuit record h include lt iostream gt include lt fstream gt include lt stdio h gt include lt stdlib h gt include lt assert h gt 10 using namespace std Normal constructor Serialisable_Circuit_Record Serialisable_Circuit_Record string location Serialisable circuit OL this gt location location this gt type PART_CLOSED so it does not show up as special 20 Load in the signature data and circuit name Load_Circuit_Directly circuit_name circuit gt Get_Circuit_Name signature circuit gt Get Circuit Signature type circuit gt Contains_Closed_Net_Vertices PART_CLOSED ALL_OPEN Special constructor 30 Serialisable Circuit Record Serialisable Circuit Record SCR Special type Serialisable switch type case SPECIAL_EMPTY circuit name _emptyycircuit_ break case SPECIAL UNIVERSAL circuit name universal circuit break case UNDEFINED break 40 default assert 0 break this gt type type circuit OL Serialisable Circuit Record Serialisable Circuit Record
34. These are stored in the circuit array and are written to disk by serialisation 5 7 4 The Database Search procedure Searching is performed by the Search procedure The procedure takes a circuit X as a parameter and can carry out three types of search using it e Find all subcircuits of X in the database e Find all supercircuits of X in the database e Find all circuits that are isomorphic to X in the database Each type of search can optionally take into account the open closed status of vertices Searches can also be set to return only the first match that is found for each database circuit which will save time if a complete list of matches within a particular circuit is not required The Search procedure operates in two stages First the matches are found using the algorithm described in Section 5 5 5 During this stage all net vertices are assumed to be open Second the results obtained in the first stage are refined if the search is required to take the open closed status of vertices into account Essentially this means re running the comparison for every subcircuit in the results that contains closed net vertices 5 7 5 Ohlrich s algorithm Ohlrich s algorithm is used by the Database class via an interface class called Circuit Manager The author wished to keep the workings of Ohlrich s algorithm separate from the workings of the Database class The functions of the two classes are entirely different and very little informatio
35. amp out const virtual bool Read std ifstream amp in virtual void Debug void const private private variables Serialisable String circuit name Serialisable String location Serialisable Signature signature SCR Special type Circuit Manager x circuit y namespace std Hendif D 15 libcrdb include serialisable int h ifndef SERIALISABLE_INT_H define SERIALISABLE_INT_H include serialisable h namespace std class Serialisable_Int public Serialisable public Serialisable Int Serialisable_Int unsigned x value x void Set unsigned x value x unsigned Get void const return value bool Write std ofstream amp out const return Write_Integer out value bool Read std ifstream amp in return Read_Integer in value virtual void Debug void const std cout lt lt value bool operator lt const Serialisable Int amp a const return Get lt a Get bool operator const Serialisable_Int amp a const return Get a Get private unsigned value k struct Serialisable_Int_Hash_Function size_t operator const Serialisable_Int amp x const Fa return size t x Get p namespace std Hendif Project Source Code libcrdb include serialisable map h 110 D 16 libcrdb include se
36. ek dev pin dev pin if edge records count ek 0 Create a new edge info record ei new Edge Info ei gt dev dev ei gt net net ei gt dev pin dev pin ei assigned false edge records ek ei edge record list push front ei else Retrieve existing record from the hash ei edge records ek recompute the weight dev net assignments may have changed ei gt weight Get Luellau Weight dev gt type dev pin if dev gt assigned ei gt weight DEV_ASSIGNED f net gt assigned ei gt weight NET_ASSIGNED eturn ei void Luellau_Circuit Get Edges Net Vertex net Edge Map amp es bool unique Net Vertex Connection List Iter cli Weight List unmark Weight List Iter uli for cli net connections begin cli net gt connections end cli Device_Vertex dev cli gt device Pin dev_pin cli gt device_pin Edge Info x ei Edge Record dev net dev pin int weight ei gt weight f ei assigned continue f es count weight 0 m me a mo We haven t seen any edges with this weight es weight ei Project Source Code 139 libcrdb src luellau circuit cc operations 800 else if unique We have seen an earlier edge with this weight s
37. gt typedef unsigned Circuit Number typedef unsigned Edge Degree typedef unsigned Topological Order struct Circuit Map Unsigned Map struct Circuit Hash Map gnu cxx hash map Circuit Number Edge Degree gt typedef std pair Topological Order Circuit Number To Be Checked Queue Item struct To Be Checked Comparison t bool operator const To Be Checked Queue Item x const To Be Checked Queue Item y const return x first lt y first L3 struct To Be Checked Queue Std priority queue To Be Checked Queue Item std vector To Be Checked Queue Item To Be Checked Comparison gt enum To Be Checked Queue Type SUB TO SUPER SUPER TO SUB struct Database Record Serialisable Circuit Record cr Topological_Order sub_to_super_order Topological_Order super to sub order Circuit Map supers Project Source Code libcrdb include luellau circuit h 102 Circuit Map subs ds private variables 100 Database Record db unsigned db size Circuit List circuit list bool ready private procedures void Make Link Circuit Number sub number Circuit Number super number bool Is Link Between Circuit Number sub number Circuit Number super_number void Remove Transitive Links Circuit Number sub number 110 Circuit Number super number void Merge To Be Checked Queue amp out To Be Checked Queue Type queue type const
38. no progress dvpl empty if comparison conflict 580 debug CYCLE AcNn cycle A cycle j while net stack empty amp amp comparison conflict Net_Vertex nvp net_stack front 590 net_stack pop_front assert nvp gt assigned Net_Vertex nv nvp gt matches assert nv gt assigned debug NV Testingymatchyof Adi to AdNn nvp gt number nv gt number Edge_Map nvpl 600 Edge_Map nvl Find unique leg pairs incident to nvp that gt Get_Unique_Edges nvp nvpl Find unique leg pairs incident to nv this Get Unique Edges nv nvl For all unique leg pairs compare the device vertices connected to them You should be able to match them all up Store each 610 device in the device stack if successful If not then comparison conflict Redo from start if nvp open amp amp nvl size nvpl size debug Comparison conflict on number of_edgesu duvsu d Nn nvpl size nvl size comparison conflict true break 620 Edge_Map_Iter emi emi size lt c for emi nvpl begin emi nvpl end emi int weight emi first Edge Info x eip emi second 630 Edge Info x el i if nvl count weight 0 Edge_Map nvl_2 debug Possible conflict edgeyof weight A
39. struct Spice Model Map std map Spice Model Name Type a list of strings struct String List Constant_Time_List lt string gt represents a subcircuit struct Spice Subcircuit External Net Vertex Map external nodes String List description ys a mapping of subcircuit names to subcircuit structures struct Spice_Subcircuit_Map std map lt Spice_Subcircuit_Name Spice_Subcircuit gt for serialisation Serialisable_String Type_To_String Type t const Type String To Type Serialisable String amp s const variables Spice Subcircuit Map Spice subcircuits Spice Model Map Spice models iterators typename typedef Spice Subcircuit Map iterator Spice Subcircuit Map Iter typedef String List const iterator String List Iter utility functions for text parsing string Get Word char x line void Eat Leading Spaces char line bool Directive Is const char line const char dir utility function to get a Net Vertex for a SPICE node number Net Vertex Get Spice Node Spice Node Number nn Spice Node Map amp node map utility function for reading a node number from a line of text Spice Node Number Get Net Vertex Number char line connectedness checking void Test Net Connectedness Net Vertex v void Test Device Connectedness Device Vertex v string Int To String int i file
40. 30 define MAGIC 0x3c063da4 gt data x x magic static char C_String const string amp s static char C_String int i static void Free String char str static CR Error Code Validate Handle CR_Handle db bool check db true static CR Error Code Translate Exception const char ex 40 Start of functions that must be available from C CR Error Code CR Create Handle CR Handle db try db new _CR_Handle mag db MAGIC ptr db OL catch 50 return CR OK return CR OUT OF MEMORY CR Error Code CR Create Database CR Handle db 60 CR_Error_Code rc Validate_Handle db false if rc CR_OK return rc Project Source Code src interface cc 182 if ptr db OL return CR_DATABASE_ALREADY_EXISTS try 70 ptr db new Database catch return CR OUT OF MEMORY return CR OK 80 CR Error Code CR Add Circuit CR Handle db const char c file CR Error Code rc Validate Handle db if rc CR OK return rc try Serialisable Circuit Record circuit Serialisable Circuit Record string c file ptr db gt Add Circuit circuit 90 catch const char ex return CR OK return Translate Exception ex 100 CR Error Code CR Build CR Handle db CR_Error_Code rc V
41. A using Search and store them in set Rsub 3 Find all supercircuits of A using Search and store them in set Rsuper 4 For each circuit B in the database do the following a Run Ohlrich s algorithm to test if A is a subcircuit of B Store the result of this com parison true or false in a b Run Ohlrich s algorithm to test if B is a subcircuit of A Store the result of this com parison true or false in 6 52 A Graph Matching Search Algorithm for an Electronic Circuit Repository c Check that B Reuper 5 If this comparison is false the test has failed d Check that B Ryu 5 8 If this comparison is false the test has failed Automatic Test Program An earlier test program that compared Luellau s algorithm and Ohlrich s algorithm was extended to include the tests described in this section This program named ohlrich vs luellau vs db cc carries out all of the tests described in this section and the non random ones described in Section The program was successfully run on a corpus of 27 test circuits and reported no errors Serialisation Tests Serialisation is used extensively by the circuit repository software the database and all the objects within it are written to disk by serialisation It is essential that no information in any object is ever lost during both serialisation and deserialisation In order to check this a variety of serialisation test cases were written as part of a program called se
42. Database Debug Map const Circuit Map amp m Circuit_Map const_iterator A 3 ce i m begin i m end i if i m begin 340 cout lt lt lt lt xi first lt lt lt lt x i second lt lt cout lt lt void Database Debug void string delim assert ready 350 cout lt lt Database contains lt lt db size lt lt ucircuits n for Circuit Number i 0 i lt db_size i cout lt lt DAGDATA lt lt delim lt lt i lt lt delim lt lt db i super_to_sub_order lt lt delim lt lt db i sub_to_super_order lt lt delim lt lt Debug_Map db i subs cout lt lt lt lt delim lt lt 360 Debug Map db i supers cout lt lt lt lt delim Project Source Code 370 380 390 400 410 420 430 libcrdb src database cc 124 lt lt db i cr Get Circuit Name lt lt An public functions void Database Build void f ready throw database already built This function will be called after every circuit has been added to the database Circuit_Number i sub_number super_number SCRI es Serialisable Circuit Record universal Serialisable Circuit Record SPECIAL UNIVERSAL Add in the Universal circuit It will be at the end of the list Add Circuit univ
43. ERROR CR WRITE FAILED 30 CR UNSUPPORTED SEARCH TYPE CR DATABASE HAS NOT BEEN BUILT CR NULL POINTER CR OTHER ERROR CR Error Code typedef enum CR_SEARCH_FOR_SUBCIRCUIT CR SEARCH FOR EQUIVALENT CR SEARCH FOR SUPERCIRCUIT CR Search Type typedef struct CR Search Flags struct 40 CR Search Type type BOOL dont assume open BOOL only find first match BOOL Sort by match size CR Search Flags typedef enum CR NET CR DEVICE CR Match Type typedef struct CR Match Items struct CR Match Type type 50 char x subcircuit item Project Source Code 60 70 80 90 10 20 97 libcrdb include circuit manager h char x struct CR Match Items struct x CR Match Items supercircuit item next typedef struct CR Match List struct double struct CR Match Items struct x _struct x struct CR Match List CR Match List typedef struct CR Result List struct char x char x struct CR Match List CR Result List typedef void CR Handle Handle x _struct x struct CR Result List struct x Score items next circuit name circuit file location next match list CR_EXT CR Error Code CR Create Handle CR Handle db CR EXT CR Error Code CR Free Handle Database generation procedures CR EXT CR Error Code CR EXT CR Error Code CR EXT CR Error Code CR Add Circuit Datab
44. Free Handle amp handle I2 CR_OK tf CR Free Handle failed 4sNMn CR Get Error String rc return 1 return 0 static void CR_Resul CR_Resul CR_Match CR_Match CR_Error int int CR_Searc flags flags flags flags rc CR_ if rc 1 prin exit result_p while prin n matc whil prin Run_Search CR_Handle handle CR Search Type search type const char search type str const char file name BOOL dont assume open t List x result list t List x result ptr List match info ptr Items x match item ptr _Code ros matches 0 n 0 h_Flags flags dont_assume_open dont_assume_open only_find_first_match FALSE type search_type sort_by_match_size FALSE Find handle amp flags file name amp result list CR_0K tf CR_Find failed 4s n CR Get Error String rc 1 tr result_list result_ptr NULL tf s u s uisvau suofu s Nn result ptr gt circuit file location result ptr gt circuit name Search type str file name 0 h info ptr result ptr gt match list e match info ptr NULL match item ptr match info ptr gt items n printf tMatchy d u score 40 3f n n match info ptr score while match item ptr NULL const char type str match item ptr gt type CR NET 7 net device
45. List change list Vertex Procedure vp For each vertex remove from the partition apply the Vertex Procedure add to the partition again ccs bool Partition Partition Change_Record new_ p clear for pi p begin pi p end iterator Vertex_List amp Vertex_List_Iter for vli region vli region vli Vertex bool re pi region vli progress false new_p pi change_item pi second begin end Project Source Code push_front net D dig 9 we don t bother to label any nodes as VDD GND have no meaning for us size PEDE bool delete unless relabelled libcrdb src ohlrich circuit cc 146 change item original weight v weight change item original open v border change item type Weight change item timecode counter 310 rc vp v progress rc progress if delete unless relabelled amp amp rc debug uuvomitteduanjitemin else 320 new p v gt weight push front v debug iwureinserted anjitem ywti din v weight Add change to change list if a there is a change list and b a change has taken place if change list NULL amp amp change item original weight v gt weight change_item original open v gt border
46. OF MEMORY A memory allocation operation failed CR UNSUPPORTED SEARCH TYPE Unsupported search type The search type must be one of the values in CR Search Type CR WRITE FAILED Writing to disk failed Table B 1 Error codes that may be returned by the circuit repository functions B 6 Demonstration applications You may find it useful to refer to the demonstration applications in cr apps which are also listed in Appendix C Three have been provided build db c page will build a database file from a list of circuits search db c page 93 will search for a particular circuit provided as a SPICE file in a particular database And dump db c page 92 will print out the contents of a database B 7 How to build a database To build a database assemble the collection of circuits that you wish to include in the database The collection may be something like the one in testcases corpus Next create a file containing the file names of every file in the corpus Each line of the file should contain a path to each file It is recommended that you supply an absolute path but this is not necessary Finally run build db with two parameters The first parameter should be the name of the database file you wish to create The second parameter should be the name of the file containing the file names created in the previous step build db will print out a warning whenever two circuits are found to be equivalent to each other It w
47. Ohlrich s algorithm makes use of the information that it has gained about the circuit during earlier matches This allows it to distinguish between vertices in circumstances where Luellau s algorithm could not Chapter 3 Evaluation of Existing Algorithms 23 A fourth advantage of Ohlrich s algorithm is that it does not use prime factors to label vertices at any time In Luellau s algorithm prime factors were used because they always uniquely identify a particular set of connections and can also be used to detect if one set of connections is a subset of another Ohlrich s algorithm never needs to check for the second condition because it handles open vertices differently to Luellau s algorithm So there is no particular reason to use prime factors provided that labels that uniquely identify a set of connections can still be generated The result is that arithmetic overflow presents no problems to Ohlrich s algorithm and the algorithm can work with arbitrarily large numbers of connections to a single vertex Finally Ohlrich s algorithm returns more information than just yes or no It is able to indicate the number of instances of subgraph isomorphism that were found If the smaller circuit can be fitted into the larger circuit in two different ways then the algorithm will be able to indicate this 3 3 4 Testing the implementation All of the tests that were performed on the Luellau Circuit class were repeated for Ohlrich Circui
48. PART CLOSED ALL OPEN UNDEFINED constructors destructors Serialisable Circuit Record std Serialisable Circuit Record SCR Special type UNDEFINED virtual Serialisable Circuit Record copy assign is allowed Serialisable Circuit Record amp operator const Serialisable Circuit Record amp c public procedures std std bool bool bool Returns the number of times that sub is a subcircuit of Handles the universal and empty circuits properly int Is Subcircuit Serialisable Circuit Record amp sub string Get Circuit Name void const return circuit name string Get Circuit Location void const return location Contains Closed Net Vertices void const return type PART CLOSED Is Special void const return type SPECIAL EMPTY type SPECIAL UNIVERSAL Test Connectedness string amp o std Match Record List amp mrl bool assume all vertices are open bool only find one match bool sort by size Project Source Code D string location but the circuit must be reloaded Serialisable Circuit Record const Serialisable Circuit Record amp c 60 TO 10 20 30 40 109 libcrdb include serialisable list h bool Is Signature Subset Serialisable Circuit Record amp sub const void Load Circuit Directly void virtual bool Write std ofstream
49. Serialisable_String type_str unsigned j num_connections Device Vertex Connection Map amp dvcm dev gt connections master device list push back dev rc rc amp amp dev gt model Read in rc rc amp amp dev name Read in rc rc amp amp type_str Read in 730 dev type String To Type type str dev gt assigned false dev gt open false dev is net false dev gt matches OL if dev gt type UNKNOWN cerr lt lt Unknown device type jread n rc false 740 rc rc amp amp Read_Integer in num_connections for j 0 j lt num_connections j Pin pin_number unsigned net_number unsigned net_info Net Vertex net 750 rc rc amp amp Read Integer in pin number rc rc amp amp Read Integer in net number rc rc amp amp Read Integer in net info if Lt re break 760 Get the Net Vertex pointer or eate it if nets count net number 1 net nets net number else net new Net_Vertex net gt number net info amp IS_OPEN net gt open net info amp IS OPEN true false net gt assigned false 770 net gt is net true net gt connections clear net gt matches OL master_net_list push_front net nets net_number net Project Source Code 780 790
50. _Tp class _Compare std less Key class _Alloc std allocator lt std pair lt const _Key _Tp gt gt gt class Serialisable_Map public public std map c Key _Tp _Compare Alloc public Serialisable Serialisable Map std mapc Key Tp _Compare Alloc bool Write std ofstream amp out const ys typedef typename std map lt _Key _Tp _Compare _Alloc gt const_iterator IV IV LA Begin by writing the size of the map if Write_Integer out size return false Then write out each pair of elements for i this gt begin i this gt end i const std pair lt _Key _Tp gt amp item x i if item first Write out amp amp item second Write out 1 return false return true bool Read std ifstream amp in ys unsigned read_size unsigned is if Read_Integer in read_size return false clear for i 0 i lt read_size i std pair lt _Key _Tp gt new item if new item first Read in amp amp new item second Read in return false insert end new_item return true void Debug void const Project Source Code libcrdb include serialisable set h 112 typedef typename std map lt _Key _Tp _Compare _Alloc gt const_iterator IV for IV i this g
51. a circuit taken from a description in SPICE format and applies a specialised subgraph isomorphism algorithm by Ohlrich 15 to compare circuits It also applies a new search algorithm developed as a part of this project to minimise the number of circuits in the repository that need to be examined The algorithm makes use of the transitive property of the subcircuit relation to eliminate circuits from consideration All of the design objectives for the tool have been met Tests show that it can run within the appropriate Unix environment can be used by C programs and that it matches any type of circuit correctly and quickly The author has no doubt whatsoever that it is fit for the purpose for which it was designed However there is scope for improvement in three areas which will now be discussed Two of the improvements are essentially extensions to the work that has already been done The third would involve a substantial redesign although some software components could be reused 8 1 Improving the Efficiency Using Dummy Circuits It was noted in Section 5 6 2 that the efficiency of the search is very dependent on the number of circuits that can be eliminated from consideration at an early stage It was suggested that some dummy circuits might be added to the database with the intention of eliminating more circuits early in the matching process Consider the part of graph illustrated in Figure This is a pathological example of a circu
52. and destroy memory areas for data As a result of this the user of the interface must free the memory used to store the results after use or introduce a memory leak The interface provides a function to do this called CR Free Result List Another disadvantage of C is that it has no way to handle exceptions Exceptions are a feature of C that is used by the database code to report errors such as file not found and out of memory Using exceptions means that there is no need to fill the code with checks to make sure that each function call succeeds if an exception occurs the computer automatically begins executing exception handling code Because C does not have this feature any exceptions that are thrown during the execution of database functions must be translated to C s nearest equivalent the error return code Every function in the interface returns an error code The code is an enumerated type with many values indicating different types of error and one value indicating success Any C program that makes use of the functions in the interface must explicitly check the error code returned by each function to ensure it succeeded For more information about the C interface for the search tool and database refer to Appendices B and C 5 7 7 Features that were not implemented The implementation resulted in a working version of the circuit repository software However two non essential features were not implemented These are de
53. be matched if they have the same function The rule based system is extensible Takashima explains that this allows his system to prove that two circuits are the same even if one of them has been optimised into an eguivalent but less complex circuit It is guite common for a mask designer to make optimisations to the circuit during design and these make it difficult for systems such as Ablasser s to show that the circuits are equivalent The techniques described by Takashima are said to be very fast even on circuits with tens of thousands of transistors The slowest part of the process is the rule based comparison This was found to be a serious problem by Spickelmier However Takashima has prevented this from being a problem by doing as much work as possible by graph isomorphism and circuit reduction Like Spickelmier s method Takashima s method has the potential to match circuits that have the same function but a different structure This means that it could be a useful teaching aid Unlike Spickelmier s system however rules are not needed for all types of matching They are only needed for cases where the graph isomorphism process cannot find a match Fewer matching rules would be needed 2 4 4 Consolidation The three papers that have been reviewed so far have described methods for comparing complete circuits This is not really what is needed when students are searching for a circuit in a database they must not be limited to exact mat
54. by the user If X is a subcircuit of Y and Y is a subcircuit of X then X and Y are isomorphic to each other So isomorphic circuits can be detected by searching for both subcircuits and supercircuits and then taking the intersection of the set of results from both or by searching for subcircuits and testing each result to see if it is also a supercircuit This allows the third type of search listed in Section 5 1 to be applied 5 5 9 A flaw in the algorithm the open nodes problem The algorithm has a flaw that results from a guirk of Ohlrich s algorithm related to the problem of open vertices that was described in Section 5 3 2 It has been assumed that the subcircuit relation is transitive This is not necessarily the case if net vertices can be closed it is possible to construct circuits A B and C such that A is a subcircuit of B and B is a subcircuit of C but A is not a subcircuit of C Figure 5 6 illustrates three circuits with this property The problem arises because of the vertex labelled as x In circuit A this vertex is closed so no supercircuit of A can extend that vertex This is why C is not a supercircuit of A a capacitor has been added which is connected to z But in circuit B vertex x is not closed It can be extended which is why C is a supercircuit of B Chapter 5 Development of an Optimised Search Method 39 X x x Xx o Open Net Vertex A B C Closed Net Vertex Figure 5 6 A is a subcircu
55. calculated by Gnuplot The line is shown on Figure This strongly suggests that on average the time complexity of Ohlrich s algorithm is something in the region of O n It must be pointed out that the worst case time complexity cannot be better than O e due to the NP complete nature of the problem being solved However it is clear that Ohlrich s algorithm performs better than this even when large circuits are being compared From this we can infer that the average time complexity of the search algorithm is also approx imately O n All of the operations carried out by the search algorithm with the exception of Ohlrich s algorithm have either linear or logarithmic time complexity if the optimal data structures are used as discussed in Section Therefore only Ohlrich s algorithm affects the time bound of the search algorithm and if Ohlrich s algorithm generally completes in O n operations the search algorithm will also complete in O n operations This is certainly computationally tractable and the results obtained indicate that searches complete fast enough to be used interactively in most Chapter 7 Evaluation 59 Time Taken Per Search millisecond Figure 7 5 The correspondence between circuit size and 10000 1000 B H ES pi Q9 x ed eu Trage si 100 0 50 100 150 200 Number of Devices in Supercircuit ered from 12 010 random circuit comparisons Time Taken Per Search millisecond Figure 7 6 The worst ca
56. case H Current controlled voltage source case V Voltage source case I Current source return default cerr lt lt Unsupportedydeviceutype u lt lt name 0 lt lt An 270 throw file_format_error return create the device Device_Vertex device new Device_Vertex device gt type type device gt assigned false 280 device gt open false device gt is_net false device gt matches OL make the connections for Pin pin 0 pin lt ext nodes pin Get the next node number and translate it to a node pointer creating a new node if necessary 290 Spice_Node_Number nn Get Net Vertex Number amp line Net Vertex net Get Spice Node nn node map Produce a Net Vertex Connection structure for this connection Net Vertex Connection connection new Net Vertex Connection connection gt device pin pin connection gt device device 300 Add the Net Vertex Connection to the net net gt connections push front connection Add a connection in the reverse direction device gt connections pin net Store the Net_Vertex_Connection on the master list for deleting it master_connection_list push_front connection Add model information to the device if any Eat_Leading_Spaces amp line if line NULL 310 Proje
57. circuit are misleading They are not exten sions to the original circuit or improvements to it they are entirely different circuits in which the existence of the original circuit is merely a coincidence There is no way to represent open and closed vertices in SPICE One method would involve the addition of specially formatted comments to every SPICE file to indicate which vertices should be considered to be open or closed In this way the SPICE files would still be readable by SPICE but the extra information would be available to the circuit repository software However a more elegant method would make use of the subcircuit feature that is already built into SPICE A SPICE subcircuit incorporates internal vertices that are only accessible within the subcircuit It is natural to assume that these internal vertices should be closed after all they are not reachable from components outside the subcircuit Additionally any extension of a particular circuit would have to have the same SPICE subcircuits with it So any vertex within a SPICE subcircuit can be assumed to be closed and all other vertices can be assumed to be open This method appears to be an ideal match for the hierarchical way that SPICE circuits are designed Power Supply Devices SPICE includes some special devices to represent voltage and current sources It was decided that these devices should be omitted from the graph representation because they provide no reliable informatio
58. circuit used by Ablasser Ohlrich and Luellau allows a device to have more than two connections unlike the representation suggested in Figure Additionally when n devices are connected to a single point only n connections are needed to that point instead of the O n connections that would be required using the Figure 1 1 representation 3 1 4 Implementing the SPICE Interpreter SPICE Interpreter was written as a single C class It translates a circuit description in the SPICE format as described in Section 3 1 1 into a variety of C data structures The constructor of the class is given a file name as a parameter It reads the file expanding all SPICE subcircuits so that the entire circuit is flattened into a single graph The graph consists of device and net vertices The data structures that are produced are as follows e A Device Vertex object is produced for each device The object includes information about the device type and model number and a list of connections e A Net Vertex object is produced for each net vertex connection point The object includes a list of connections e Each connection is described by a Net Vertex Connection structure e Three master lists are produced containing all net vertices device vertices and connections respectively These make it easy to apply an operation to every vertex or edge and to destroy the data structures when the SPICE Interpreter object is deleted 16 A Graph
59. empty partition Partition amp subgraph_partition_copy net_subgraph_partition_copy 920 Partition amp graph_partition_copy net_graph_partition_copy Project Source Code libcrdb src ohlrich circuit cc 154 if net subgraph partition copy empty dev_subgraph_partition_copy empty amp amp dev_subgraph_partition_copy size lt net_subgraph_partition_copy size subgraph partition copy dev_subgraph_partition_copy graph partition copy dev graph partition copy 930 assert subgraph partition copy empty debug No moreyuprogress 4d unmatched partitions Nn subgraph partition copy size Pick a keynode from that and recurse into it for pi subgraph partition copy begin pi subgraph partition copy end pi 940 1 int weight pi first Vertex List amp sub region pi second assert sub region size gt 1 if graph partition copy count weight 1 Vertex List amp region graph partition copy weight The items in sub region are the keynodes 950 region is our candidate vector Vertex x new keynode sub region begin int mc2 Verify Image new keynode region if mc2 gt 0 We have succeeded mc mc2 960 if only find one match 1 Back Out Relabelling NULL amp change list return mc else break else debug Fai
60. header file called interface h This header file needs to be tincluded by any C program wishing to use the search tool It gives access to a number of C functions that allow Database objects to be accessed from C Complete documentation for the interface has been included in Appendices B and By design the interface does not use any global variables Instead it works using handles Handles identify a particular database session Hidden within each handle is a pointer to the underlying Database object but this information is used only by the interface functions The fact that global variables are avoided means that the interface and database library can be placed inside a shared object It is also thread safe to some extent A side effect of the use of handles is that several databases may be open at a time which may be useful for testing purposes The interface has to convert all parameters from C types to C types and back again The main place where this has to be done is in the CR Find function which carries out a database search Here the search results must be converted from a C type they are stored as an STL list to a C type a simple singly linked list This is done in the interface code One disadvantage of C data structures is that the memory for them has to be allocated and freed explicitly In C and STL the data structures can manage this operation on the programmer s behalf But in C malloc and free are required to create
61. horribly inefficient 30 Match Record match records array new Match Record num_matches Match Record List iterator m size t i 0 for m mrl begin m mrl end m match records array i m Lour 40 Now sort the array if sort_by_size sort match_records_array match records array num matches Sort By Size else sort match_records_array match_records_array num_matches Sort_By_Score 50 And convert it back to a linked list mrl clear for i 0 i lt num_matches i mrl push back Match_Record match_records_array i delete match_records_array return ret_code 60 Project Source Code 159 libcrdb src scored circuit cc void Scored Circuit Build Match Record Spice Interpreter that 1 Device_Vertex_List_Iter dli double score 1 0 const double lambda 2 0 build the match record Spice_Interpreter Build_Match_Record that 70 calculate the score for dli master_device_list begin dli master device list end dli if dli assigned continue double value_x Get Value dli 80 double value_y Get Value dli gt matches if value x lt 0 0 value_y lt 0 0 we can t score this continue else if value_x gt value_y score pow value_y value
62. if n youywish to startjaynew database MESSAGE CR_FILE_FORMAT_ERROR The formatyof ja yfileyjon disk jisyincorrect MESSAGE CR WRITE FAILED Writing yto disk failed MESSAGE CR_UNSUPPORTED_SEARCH_TYPE Unsupported search type n 1 The searchytypeyumust bey one of the values in CR Search Type MESSAGE CR DATABASE HAS NOT BEEN BUILT The database has not been built yet You must build itin before writing it to ydiskyjor searching it MESSAGE CR NULL POINTER A null pointer was givenyjas ja parameter MESSAGE CR OTHER ERROR An unknownyerror occurred Youymay need n to debug the software asyityjis likely that jan jassertion n has failed n default return Unknown error code CR Error Code CR Debug CR Handle db CR_Error_Code rc Validate_Handle db if rc CR_OK return rc ptr db Debug return CR OK End of functions that must be available from C x static CR Error Code Validate Handle CR_Handle db bool check db T A cg return CR NULL POINTER db OL amp mag db MAGIC return CR INVALID HANDLE f check db amp ptr db OL return CR NO DATABASE return CR OK static void Free String char str if str OL Project Source Code 187 src interface cc 450 1 throw nullupointer
63. matches that are found must have exactly the same device values It will also be possible to assign a score to each match that is found according to how closely the device values matched However the algorithms that have been looked at so far are not necessarily the best way to achieve this To search a database of m circuits using any of the algorithms would take at least mn operations if each circuit contained at least n components This is not ideal But not all search methods need to take this long If a program was searching a dictionary for a word it could search through all possible words until the word was found This would be a linear time operation It would be better to sort the dictionary in alphabetical order because this would allow a binary search to be used This would complete faster in O log n time for n words It would be even better to store the words in a hash table Then it would be possible to find a word in the dictionary in constant O 1 time It should not be a surprise then that this last technique is the one that is used in spell checking software Related techniques can be applied to circuit matching When this project was started it was not clear what they would involve and to date no researchers appear to have addressed this problem However research undertaken by the author has led to the development of a database structure that allows the number of circuits that need to be examined to be minimised This structu
64. next letter if the current letter is the same in both words In the case of circuit comparison Ohlrich s algorithm provides the comparison method The search method is yet to be defined but it cannot be the naive method of scanning every circuit in turn just as a dictionary search should avoid examining every word until the correct one was found So one way to improve the speed of searches is to improve the speed of Ohlrich s algorithm The algorithm appears to be highly optimised However one area for improvement lies in the data structures that it uses 4 1 Hash tables or red black trees The paper 15 does not recommend any particular data structures for use in the implementation of the algorithm However the original implementation of the algorithm obtained courtesy of staff at the University of Washington does provide a guide Practically all the structures that are present in the original implementation are open hash tables which are excellent structures to be used whenever random access is required to some data by some type of key In Ohlrich s algorithm the data is a list of vertices and the key is the label assigned to all of those vertices The choice of hash tables is a mistake Ohlrich s algorithm regularly requires all vertices to be examined by a relabelling process and in order to achieve this the algorithm iterates through every member of the hash table Hash tables are not efficient when they are used in this fashion bec
65. one db sub_number supers erase super_number db super_number subs erase sub_number 150 void Database Sub_To_Super_Set_Topological_Order Circuit_Number circuit_num Topological_Order order Circuit_Map iterator child Set the order of this circuit if db circuit num sub_to_super_order lt order 160 db circuit num sub to super order order order db circuit num sub_to_super_order 1 Set the order of the children for child db circuit_num supers begin child db circuit num supers end child 170 void Database Super_To_Sub_Set_Topological_Order Circuit_Number circuit_num Topological_Order order Sub_To_Super_Set_Topological_Order child first order Circuit_Map iterator child Set the order of this circuit 180 if db circuit num super_to_sub_order lt order db circuit num super_to_sub_order order order db circuit num super_to_sub_order 1 Set the order of the children for child db circuit num subs begin child db circuit num subs end child 190 Super_To_Sub_Set_Topological_Order child first order The circuit map in is merged into the to be checked queue out void Database Merge To_Be_Checked_Queue amp out To_Be_Checked_Queue_Type queue_type 20
66. parsing functions void Read Model char line void Read Spice File istream amp fd void Read Subcircuit Device Vertex char line Spice Node Map amp parent nodes void Read Subcircuit istream amp fd char line void Read Device Vertex char line Spice Node Map amp node map public inline int debug const char format ifndef DEBUG void format return 0 else va_list ap Project Source Code 270 1 2 3 4 e 0 0 0 0 0 libcrdb src circuit manager cc 118 ys Hendif y int n const int buf_size 128 char buf buf_size 1 va_start ap format n vsnprintf buf buf size format ap va end ap cout lt lt buf return n namespace std Hendif D 22 include include include include libcrdb src circuit manager cc circuit_manager h lt iostream gt lt fstream gt lt string h gt using namespace std Circuit_ ifst circ Circuit_ 1 Circuit_ circ Manager Circuit_Manager const std string amp location Serialisable ream fd location c_str uit new Scored_Circuit fd Manager Circuit_Manager Serialisable uit new Scored_Circuit Manager Circuit Manager delete circuit int Circ 1 Hifdef D cout Hendif int Hifdef D cout Hendif uit Manager Is Subcircu
67. pico exponent 1E 12 done true break case F femto exponent 1E 15 done true break case E exponent form this is handled by the C library strtod function exponent 1 0 done true break f done isspace value str i break char error double value strtod value_str amp error if error value_str return 1 0 can t decode it else if value lt 0 0 this is not valid component values are scalars return 1 0 return value exponent D 28 libcrdb src serialisable cc include serialisable h include lt netinet in h gt When accessing the file in binary mode we use the network byte order This will make the db portable between big and little endian machines Also ints are always written as 32 bit TODO does it work with 64 bit ints 16 bit ints define BINARY MODE static const unsigned MAGIC NUMBER 1 0x60ecaf3e Project Source Code 20 30 40 60 70 80 90 161 libcrdb src serialisable cc using namespace std bool Serialisable Write Integer ofstream amp out unsigned x const ifdef BINARY_MODE uint32_t xi htonl uint32_t x out write const char amp xi sizeof xi return true else out lt lt x lt lt Nn return true Hendif boo
68. subjects for further work There may well be a benefit to adding them but it is a subject for future investigation 8 2 Improved Techniques for Eliminating Circuits This project has examined the effectiveness of using Ohlrich s algorithm to find subcircuits and supercircuits in a database combined with a search algorithm that ensures that circuits are not needlessly tested by Ohlrich s algorithm The author believes that this project represents the first time that such techniques have been used to match circuits probably because this is the first time there has ever been a need for a circuit database that can be searched quickly and automatically However this is not the first time that related problems have been addressed The best example comes from the field of bioinformatics Pharmacologists often need to search for molecules with a particular structure when designing new drugs it can often be assumed that a similar structure implies similar behaviour In order to make this possible large databases of molecules have been built 21 and tools exist to search them 20 22 The molecules are expressed as graphs in the database and searching for a particular structure is a subgraph isomorphism problem It is very similar to the subgraph isomorphism problem handled here both because a large number of molecules must be tested and because each graph can be labelled to some extent While a graph of a circuit is labelled with device types and val
69. such as a logic gate is described by a rule The rule describes what basic components transistors etc make up the functional block Sometimes a functional block may take one of several forms in this case several rules may exist to match it Then the program describes the entire circuit to be matched in rule form The low level connections between basic components are listed each link as a single rule This method of matching handles certain special cases very well It is good at distinguishing parts of the circuit that are very similar such as memory cells in a RAM It can also cope well with permutations in the circuit For instance the inputs to an AND gate may be connected in any order But other comparison algorithms may insist that the order is exactly the same in both circuits being compared The method also makes it easy to specify rules for functional isomorphism Two circuits that are functionally isomorphic have the same function but may have entirely different structures However the method is generally rather slow It appears that it has poor time and storage complexity although the paper does not state the exact complexity noting only that subcircuits with many elements increase the run time significantly Spickelmier s method is of particular interest because it could allow a circuit drawn by a student to be matched with one in the database even if the two had the same function but a different structure The method
70. test tool and stored in SPICE format The circuit contained a random non zero number of components connected together randomly A supercircuit of that circuit was then constructed by adding a random number of additional components to it The test tool then ran the following tests using Ohlrich s algorithm e The smaller circuit is a subcircuit of itself e The larger circuit is a subcircuit of itself e The smaller circuit is a subcircuit of the larger one e The larger circuit is not a subcircuit of the smaller one Since the circuits are generated the correspondence between each subcircuit vertex and each supercircuit vertex is always precisely known and this correspondence was checked by the test tool to ensure that Ohlrich s algorithm found the exact match The test tool examined huge numbers of these circuits It was left running for a day and it tested 115 548 different circuits All of the checks listed above passed for every circuit Of course this test only really shows that Ohlrich s algorithm can find positive examples places where the smaller circuit is a subcircuit of the larger one The fourth check is intended to find a negative example but its value is limited The larger circuit cannot possibly be a subcircuit of the smaller one since it has more components However the other tests show that Ohlrich s algorithm can identify negative examples correctly 24 A Graph Matching Search Algorithm for an Electronic Circuit Repo
71. that gt starting device vertex gt name c str dv_match name c_str switch rc case OK debug yes n break case NO UNIQUE EDGES cant true can t do it fall through case COMPARISON CONFLICT 370 debug no n this gt Manipulate Flags CLEAR UNFINALISED that gt Manipulate Flags CLEAR UNFINALISED break else Starting at a net vertex The start net vertex is guaranteed to be closed so we don t need to worry about matching open net vertices 380 which is hard Net_Vertex_List corresponds net list by weight that gt starting net vertex gt weight Net Vertex List iterator nvi for n n Net_Vertex nv_match nvi vi corresponds begin vi corresponds end amp amp rc OK nvi 390 if nv_match gt assigned debug Net Vertex Matching Weuwilluguessuthatu ducorrespondsutoy4d Nn that gt starting_net_vertex gt number nv_match gt number continue 400 net_stack clear device_stack clear put it on the net vertex stack net_stack push_front that gt starting_net_vertex mark the correspondence assert that gt starting net vertex gt assigned assert nv match gt assigned that gt starting net vertex gt matches nv match 410 that
72. that a correct part of graph is generated by the database Build function An incorrect graph will lead to incorrect assumptions being made by the Search function and these will cause erroneous results The author decided that one way to examine the structure would be to draw the graph from information contained in the database This is a time consuming process which is prone to error for a database of any appreciable size if it is done by hand However special debugging procedures could be added to the search function so that it prints out information about the connections in the graph This would make the job of drawing the graph a little easier but it would still take a long time Alternatively the part of graph could be drawn by a program Rather than write new software to draw the graph an existing program named daVinci 9 was used for this Graph drawing software is not easy to write even if the graph is acyclic as in this case The programmer needs to come up with ways to arrange the vertices of the graph in a way that makes the structure clear while still ensuring that the graph that is drawn correctly represents the data daVinci does exactly this it even allows a user to move vertices around to improve the clarity By using daVinci the extra implementation time needed to visualise the database structure is minimised A procedure named Debug was added to the Database class This procedure writes the contents of the database to the st
73. that could solve the decision problem within a provable time bound at least for certain types of graph Corneil described such an algorithm It was able to detect graph isomorphism in O n steps in certain cases specifically in the case of graphs containing no strongly regular transitive subgraphs Corneil defines a transitive subgraph as a subgraph that reoccurs in more than one place in the whole graph Such a subgraph is strongly regular if each vertex has the same number of neighbours It was thus possible to solve graph isomorphism problems in polynomial time at least in some cases The importance of this will be explained later 2 2 What is subgraph isomorphism Subgraph isomorphism is a more general case of graph isomorphism in which the graphs do not necessarily have to have the same numbers of vertices and edges F igure 2 2 shows an example S G Figure 2 2 S is an isomorphic subgraph of G it contains a subset of the vertices of G All of those vertices are connected by the same edges that appear in G A subgraph S Vs Es of a graph G V Ey has a subset of the vertices of G V C Vg Every edge that connects vertices that are in G and S is present in both G and S All of the edges that appear in G and link vertices in S are also present in S An isomorphic subgraph S Vy Es of a graph G is similar to this but it does not necessarily have any vertices in common with G The only thing that S and G hav
74. that satisfies all data pairs x y can be found This gives the equation of the worst case bound because a is based upon the worst example found in the data set A second graph shown in Figure was plotted from the data This graph includes a worst case time bound computed using the process described in the previous paragraph As can be seen the bound line is far steeper than the general trend It is immediately clear that the time taken by Ohlrich s algorithm is generally far less than that predicted by an exponential bound This is a similar finding to results obtained by Ohlrich s team The paper 15 suggests that the average time taken by the algorithm is polynomial in the number of vertices present Further evidence from this comes from the fact that a line of best fit can be plotted through the data with a fourth order polynomial equation The Gnuplot 32 graph plotting software that was used to draw Figure 7 6 can compute a line of best fit for a data set according to a polynomial equation provided by the user It is possible to provide Gnuplot with an equation such as f x az bx c and have it find the values of a b and c that best fit the data Gnuplot minimises the square of the distance between each data point x y and x f x in order to do this Provided that the equation of the line of best fit is at least a fourth order polynomial that is one including a term raised to the power of 4 an excellent fit for the data can be
75. the database software can be expressed as a set of integers and strings 5 7 2 Byte order Integers can be stored on disk in string form by converting them into a decimal representation However it was decided that this should be avoided because decimal binary conversion is an unnecessary step that would slow down the loading of the database So integers are serialised by writing them directly to disk as a 32 bit binary number There is one disadvantage to doing this the order of the bytes that are written to disk depends on the nature of the system that is writing them For example an Intel compatible processor stores an integer in little endian form meaning that the byte at the lowest address in memory is the least significant However many other pro cessors including MIPS and SPARC store integers in big endian form with the most significant byte at the lowest address in memory This is an important issue as the Book Emulator is a multi platform program and it is expected to operate correctly on all platforms It would be very inconvenient if a database generated on an Intel system couldn t be used on a MIPS system In order to avoid this problem integers are converted to big endian form before being written to disk The Unix C library provides standard functions to do this such as htonl and htons They are converted back to the byte order of the host system when they are read in 42 A Graph Matching Search Algorithm for an
76. the original implementation of Luellau s algorithm the SubGemini source code is available and staff at the University of Washington were kind enough to send a copy to the author The source code provides two things First it is a useful reference implementation that can be used to clarify details of the algorithm that may not be clear from the paper and guide any other implementation Second it is able to solve the entire problem by itself so it is possible to analyse Ohlrich s algorithm without any additional implementation 3 3 1 Reimplement or not The availabil ty of SubGemini gave the author a choice should the algorithm be reimplemented or should the existing version be used Reusing the existing version would give two advantages The implementation was known to be correct and less work would be reguired In fact it would only be necessary to compile SubGemini on a modern computer and find a way to make it read circuits in SPICE format Neither of these were expected to be difficult However there are other disadvantages of this code reuse Firstly it is unscientific to compare two algorithms unless the environments they operate in are as similar as possible SubGemini is not only an implementation of Ohlrich s algorithm it contains procedures to read data in from files and output answers It would be unfair to compare the SubGemini program directly to the Luellau program written in Section because they have different input and out
77. the performance with larger circuits is difficult because no large circuits are available for testing Even if large circuits were entered into the database by hand it would This figure was derived by noting that approximately 68 of all samples from any Normal distribution lie within one standard deviation of the mean In this case this is the range 5 6 25 6 Since exactly 5096 of the samples will be less than the mean and 68 will be greater than it and within one standard deviation of it approximately 68 50 84 of the samples will be less than 25 6 58 A Graph Matching Search Algorithm for an Electronic Circuit Repository be difficult to get a sample of large circuits that are representative of all circuits simply because electronic circuits are very diverse Fortunately there is a way to evaluate the performance of the search tool using very large circuits In Section a test called breakdown was described This test repeatedly generates pairs of circuits at random with the property that one is a subcircuit of the other It then applies Ohlrich s algorithm to ensure that it is able to detect the subcircuit relation correctly The circuits that are generated vary in size from 2 devices to 300 devices and all circuit sizes are equally probable A circuit with 300 devices could reasonably be considered to be a very large circuit The time taken for each comparison carried out by the breakdown tool can be measured by making an e
78. they work how they are designed and perhaps suggestions of simplifications and improvements that could be made to the design This project is concerned with the development of the second and third tools listed above the first tool is being developed as part of another project The report is primarily focused on the development of the search tool since the design of the repository building tool depends entirely on the type of information that the search tool requires to speed up its operation 1 2 The environment of the search tool The search tool is one of several proposed extensions to the Book Emulator 3 Other extensions include tools to allow users to draw circuits simulate them and export them in SPICE format The search tool will eventually be integrated with the circuit drawing tool It will have a point and click interface The user will be able to start a search for a circuit fragment with a few mouse clicks and be presented with information about that fragment in the Book Emulator The Book Emulator is written in C and runs on Unix systems The software produced during this project will run in the same environment The search tool must also be able to understand the SPICE format since it is in this format that circuit information will be made available The SPICE format is a description language for electronic circuits 2 A Graph Matching Search Algorithm for an Electronic Circuit Repository 1 3 Scope of the project The p
79. to be anything other than an O 1 operation In Ohlrich s origi nal implementation of the algorithm the equivalent function NumPartitions is a constant time operation An extra variable can be added to track the number of items in the list and size can simply return the value of this variable And in this application there is every reason to make size as fast as possible size is called from several places in Ohlrich s algorithm and during a test database build involving 27 circuits size was found to be called 51 929 times Since each call required a number of operations proportional to the size of the list involved a significant amount of processor time was wasted by calls to size Chapter 4 Improvements to Ohlrich s comparison algorithm 27 A new template called Constant Time List was written to extend the STL list template This template provides a linked list with the same properties as the STL list template but the time complexity of the size function is always constant It just returns the current value of a size variable which is kept up to date by the other list functions incremented whenever new items are added and decremented when they are removed 4 3 Prepared circuits Any implementation of Ohlrich s algorithm will spend a short time preparing a circuit for compar ison This process has three parts firstly the circuit is read from a file and translated into an internal format Secondly an initial labellin
80. to collect the types of net vertex present in each circuit into a set For X that set would be abcdefg For Y it would be acefghij Although these two sets have elements in common it is not in general possible to infer anything about the relationship between X and Y by looking at the sets of net vertices that are present In particular the set for Y is not a superset of the set for X This is because an open net vertex in X may be extended in any way In this example a resistor was added to the net vertex with label b which caused label b to be replaced by j The obvious solution to this problem is to ignore all open net vertices for the purpose of making sets of net vertices that are present If this is done then only the vertex labelled g remains in the set for X Now the set for Y will be a superset of X it will certainly include g However this does introduce a subtle problem since vertices that are closed in X may be open in any of X s supercircuits provided that they are not extended For example F igure 5 2 illustrates another supercircuit of X called Z Z has the same structure as Y but every vertex in Z is open h c J P 8 a o L Y o i f Da h e Key o Open Net Vertex o o Circuit Z Closed Net Vertex Figure 5 2 Z is also a supercircuit of X but all the vertices in Z are open If all open net vertices are ignored then the set of vertices that are present in Z is
81. to pointers in many situations Unlike pointers reference types are never null and can never point to unused or unavailable memory There is also no need to allocate or free reference types memory allocation for these types is managed automatically so there is no chance of a memory leak developing More subjectively the object oriented nature of C leads to better software engineering prac tices It encourages the programmer to adopt an object oriented mindset and think carefully about the structure of the program Of course it is still possible to write poorly designed programs in C but the author has found that using C allows him to write better code The correct way to achieve something is usually apparent from the object oriented structure A C class called SPICE Interpreter was written capable of reading a SPICE circuit descrip tion and building data structures to represent the circuit These structures can be used directly by circuit matching algorithms As stated in the previous chapter circuits are considered to be bipartite graphs consisting of device vertices and net vertices Device vertices represent devices such as transistors and resistors Net vertices represent any place where two or more wires are connected This is the naming scheme used by Ohlrich 15 and it is used because it is considered to be less confusing than the equivalent naming scheme used by Ablasser 1 and Luellau 12 The representation of a
82. vastly improved The choice of a good starting point is critical to both algorithms 22 A Graph Matching Search Algorithm for an Electronic Circuit Repository Both Luellau and Ohlrich note that the running time of the gradual matching process is far greater than that of the first phase but the time spent in this phase depends on the choice of key vertex For example in the circuit in Figure 3 6 there are four transistors four resistors and one diode If an algorithm is searching for a subcircuit of Figure a diode would be an excellent choice of key vertex in the subcircuit because it can only be matched to D1 o RI R2 R4 4k 1k6 130 6 Q3 2 4 a s 1 y Fo DI i a 4 K Y L 8 Q4 10 Q R3 lk o 0 Figure 3 6 An inverter circuit reproduced from page Luellau s algorithm always chooses a starting vertex with a maximal number of unique edges When the algorithm compares Figure 3 6 with an identical circuit it chooses Q4 as the key vertex This is a very poor choice because there are three other transistors that Q4 could be matched to The gradual matching process is run three times until the correct match is made However Ohlrich s algorithm correctly selects D1 because it chooses a key vertex with the intention of minimising the size of the candidate vector As a result when Ohlrich s algorithm compares Figure 3 6 with itself the gradual matchin
83. version 3 2 3 or later If all of the above are installed but some step of the build fails ensure that the GNU versions of make and cc are being run B 2 Building the circuit repository software The source code of the circuit repository software is supplied in a gzipped tar archive that may be extracted on Unix systems with a command such as gzip cd cr tar gz tar xvf Doing this will create a subdirectory cr with the following subdirectories within it apps include libcrdb libcrdb src libcrdb include src testcases testcases corpus testcases regression T5 76 A Graph Matching Search Algorithm for an Electronic Circuit Repository The cr directory includes a Makefile that can be used to build the circuit repository library some demonstration applications and the test cases Entering make in the cr directory will start this process It is possible to run the automatic tests by entering make run_tests The test programs will terminate with an error message if any test fails The final test carries out circuit comparisons on random circuits and will run until Control C is pressed This is the test described in Section B 3 Using the circuit repository software from a C program The circuit repository software can be used from your program by copying all source and header files into an appropriate place and adding them to your build process However this is not recommended unless your program is written in C Th
84. 0 ifdef DEBUG debug Entering Verify_Image status n Print_Partition udevs this gt dev_partition Print Partition unets this gt net partition 780 endif for vli candidate_vector begin vli candidate vector end vli Change_List change_list Vertex x candidate vli bool progress true bool progress_last_time false int iterations 0 790 bool equiv_class_check_failed false bool doing_devs false Partition iterator pi Partition net_graph_partition_copy Partition net_subgraph_partition_copy Partition dev_graph_partition_copy Partition dev_subgraph_partition_copy 800 candidate is matched to keynode and marked safe Save Item On Change List amp change list candidate Everything Save Item On Change List amp change list keynode Everything Match candidate keynode ifdef DEBUG debug Beginning Verify_Image process for new match n Print Partition udevs this gt dev partition 810 Print Partition ynets this gt net partition endif relabeling doing_devs keynode gt is_net do relabel neighbours of safe nodes 820 iterations progress_last_time progress if doing_devs debug Iterationy d devices n iterations dev graph partition copy this gt dev partition dev subgraph partition copy that gt dev p
85. 0 const Circuit_Map amp in Circuit Map const iterator in iter Copy the items from the map into the To Be Checked List in iter in begin while in iter in end Project Source Code 210 220 240 250 260 270 280 libcrdb src database cc 122 Database out push To_Be_Checked_Entry gueue_type in iter Topological Order To Be Checked Queue Item Database in iter first To Be Checked Entry To Be Checked Queue Type queue type Circuit Number n const switch queue type t case SUB TO SUPER to db break break default assert break Hifdef DEBUG cout lt lt XX add lt lt db n j 0 cer lt lt u numbery lt lt n lt lt utoyheap upriorityu lt lt to lt lt An to n case SUPER TO SUB to db n sub_to_super_order super_to_sub_order Get_Circuit_Name endif note to is complemented because we want the queue to put low to values at the front return To Be Checked Queue Item to n serialisation bool Database bool Database bool rc true if ready throw database_not_built rc rc amp amp Serialisable_Int MAGIC_NUMBER_2 D Write std ofstream amp out const Write out rc rc amp amp Serialisable Int db size
86. 1 Tapa Circ E n gu A lane Ad a 1 1 CUm E n l M sala mE ton om Sras opt Wood Creat 2104 intermediate pei penur sod termediate m tpt stage I pem ee pi mom 1 2 Ta 66 PS a a I j 3 4 AND E SITAS Schematic Hex inverters Sapa NOR input AnD zon Hex inverter epen fameen mepe amete ametozoeu E E teat ct GIONI ES es ES less ent oom a 1 m m 1 i Y Tu AND input o Tn ias p10 c1 6 p38 c1 161 ta 2 1 Y Tio Eno Circuit Number gate mise 2 fenem 1 Y PUT TEST tio jut ET 2 2 Y X Zag NOR Epi amero ametot ev E m m 2 Y ZARS gato poset bai 2 Y Genet Standard wan pcr m Figure 7 7 The part of graph for the entire test corpus see Section 64 A Graph Matching Search Algorithm for an Electronic Circuit Repository Chapter 8 Conclusions and Future Work During the course of this project a search tool has been developed that can find circuits or fragments of circuits within a circuit repository The tool has been developed to meet the requirements of the Department as discussed in the first chapter It can be integrated into any C program requiring the search functionality It is expected that the tool will be added to the Book Emulator 3 software in due course The tool was developed in C with a C compatibility layer to allow it to be used with any C program It makes use of an abstract representation of
87. 6 Adding a Device Value Comparison Feature Ohlrich s algorithm has no support for comparing the values of electronic devices in the circuits that it matches Some devices have a value associated with them for example a resistor has an associated resistance and a capacitor has an associated capacitance This feature was omitted from Ohlrich s algorithm because it is specific to the particular circuit matching application and Ohlrich aimed to make the algorithm as general as possible It is important that the search algorithm does have this type of value comparison feature It will allow two new features to be added which will make the search tool more useful e Exact matching will be possible An exact match X for a circuit Y has the same structure as Y and every device in X has the same value as the equivalent device in Y The identity of the equivalent device is known it has already been determined by Ohlrich s algorithm e Match scoring will be possible Here matches found by the search algorithm will be ranked according to how closely they match the circuit provided by the user Ranking will be based on how closely the device values match A procedure will be written that compares the device values in two circuits which have been matched by the search algorithm and is able to produce an indication of how close the match was 6 1 Device Value Comparison Issues In this section the issues surrounding the comparison of device value
88. 800 810 820 830 840 libcrdb src spice interpreter cc 178 Create the connection dvcm pin_number net Produce a Net_Vertex_Connection structure for this connection Net_Vertex_Connection connection new Net_Vertex_Connection connection gt device_pin pin_number connection gt device dev Add the Net_Vertex_Connection to the net net gt connections push_front connection Store the Net_Vertex_Connection on the master list for deleting it master_connection_list push_front connection return rc void Spice_Interpreter Debug void const Device_Vertex_List_Iter const_iterator dli cout lt lt CIRCUITDATA START lt lt circuit name lt lt Nn for dli master device list begin dli master device list end dli cout lt lt DEVICE START lt lt dli name lt lt An cout lt lt DEVICE MODEL lt lt dli gt model lt lt An cout lt lt DEVICE OPEN lt lt dli gt open lt lt UFINALISED lt lt x dli gt finalised lt lt IS NET lt lt dli gt is_net lt lt y ASSIGNED lt lt dli gt assigned lt lt USAFE lt lt dli gt safe lt lt uBORDER lt lt dli gt border lt lt uWEIGHT lt lt dli gt weight lt lt uMATCHES lt lt int
89. CONSTANT_TIME_LIST_H include lt list gt include lt iostream gt include lt fstream gt finclude lt string gt include lt stdio h gt include lt assert h gt define PARANOID void Debug_XY void namespace std template lt typename _Tp typename _Alloc std allocator lt _Tp gt gt class Constant_Time_List Project Source Code izd D D 0 i 3 20 30 40 60 70 80 90 99 libcrdb include constant time list h private size t size copy list Tp _Alloc gt data public iterators typedef typename list lt _Tp typedef typename list lt _Tp typedef typename list lt _Tp constructors Constant_Time_List size_copy 0 data clear bi Constant_Time_List const size copy x si data x data y Alloc gt iterator iterator _Alloc gt const_iterator const_iterator Alloc gt reference reference Constant Time List amp x ze copy Constant Time List amp operator const Constant Time List amp x size copy x si data x data return this Ls The size function ope size_t size const ifdef PARANOID assert data s fendif return size_copy ys A small subset of the f These are the only ones bool empty const Hifdef PARANOID assert size_copy 0 data empty Hendif return size_copy al ze cop
90. Circuit Map amp in void Debug Map const Circuit Map amp m To Be Checked Queue Item To Be Checked Entry To Be Checked Queue Type queue type Circuit Number n const void Super To Sub Set Topological Order Circuit Number circuit num 120 Topological Order order void Sub To Super Set Topological Order Circuit Number circuit num Topological Order order D 9 libcrdb include luellau circuit h ifndef LUELLAU_CIRCUIT_H define LUELLAU_CIRCUIT_H include spice_interpreter h include lt ext hash_map gt include lt ext hash_set gt 10 namespace std class Luellau_Circuit public Spice_Interpreter public enum Match_Result FAIL COMPLETE REPEAT IMPOSSIBLE public functions Luellau_Circuit istream amp fd 20 virtual Luellau Circuit Match Result Compare_To Luellau Circuit kt Match Record List amp mrl unsigned long Get Number 0f Operations return operations protected struct Edge_Key 30 1 Device_Vertex dev Net Vertex net Pin dev pin y struct Edge_Info public Edge_Key public Vertex Project Source Code 103 libcrdb include luellau circuit h ys struct Edge_Hash Edge Info x matches 40 size t operator const Edge Key amp i const return size t size t i dev_pin size_t i dev size t i net L3 L3 50 Struct Edge Eq t bool operator Ed
91. Electronic Circuit Repository 5 7 3 The Database Build procedure The main functions of the Database class are provided by two procedures One provides the search functionality and another allows the database to be rebuilt It was decided to include both features in the same class for simplicity and also to ensure that any changes to one could easily be applied to the other The Build procedure builds a part of graph for all of the circuits that have been added to the database by a procedure called Add Circuit It is envisaged that a user of the database would add a number of circuits and then call Build There is no support for incremental building of the database Attempting to include this feature would unnecessarily complicate the code with no benefit since the time taken to build the database is not important The procedure operates along the lines of the algorithm described in Section It has five stages 1 The empty and universal circuits are added to the database 2 All circuits that have been added to the database are arranged into an array 3 The complete part of graph is generated by the process described in Section 5 5 4 4 Transitive edges are removed as described in Section step 5 The topological order number of each circuit in the graph is calculated using the algorithm outlined in Section 5 5 3 The procedure produces for each circuit a set of supercircuits a set of subcircuits and a topo logical order number
92. However the algorithm cannot be used by itself Ohlrich s algorithm only compares two circuits and the search tool needed to match a single circuit against a large number of circuits to find the best matches In addition Ohlrich s algorithm has no support for comparing the values of devices This had to be implemented separately and the discussion of the implementation can be found in Chapter 6 Chapter 4 Improvements to Ohlrich s comparison algorithm The project aims to produce a search tool that can compare a circuit provided by a user to a large number of circuits stored in a database In general there are two ways to optimise any search process First there is optimisation of the method by which candidates for matching are chosen which is called the search method Second there is optimisation of the comparison process that is used the comparison method The comparison method acts on two items at a time and indicates the relationship between them Consider the example of searching a dictionary for a word Here a poor search method would involve examining every word until the one being searched for was reached requiring O n compar isons for a dictionary of size n The optimum search method is a binary search because the words in the dictionary are sorted into alphabetical order O log n comparisons are required to find a word and the optimum comparison method compares words one letter at a time only advancing to the
93. Interpreter Read_Subcircuit istream amp fd char line Spice_Subcircuit_Name name Spice_Node_Number node_number int is es Spice Subcircuit subcircuit Interpret the subcircuit info void Get Word amp line Remove first word SUBCKT name Get Word amp line 2nd word subcircuit name Check that this subcircuit hasn t been seen before assert spice subcircuits count name 0 Project Source Code 173 libcrdb src spice_interpreter cc Allocate storage for this subcircuit Spice subcircuits name subcircuit new Spice Subcircuit Copy the body of the subcircuit into storage char line buffer READ LENGTH 2 bool end false while end 400 fd getline line buffer READ LENGTH assert fd good amp amp fd eof char copy_line line buffer debug RSCy s n copy_line Eat Leading Spaces amp copy line 410 switch copy line 0 case if Directive Is copy line ends end true else if Directive_Is copy_line model a device model Read_Model copy_line 420 else if Directive_Is copy_line subckt Sorry you can t have a subcircuit within a subcircuit here assert 0 break case break default 430 subcircuit gt description push_back string copy_line
94. Matching Search Algorithm for an Electronic Circuit Repository Using these data structures it is possible to traverse the entire graph starting at a single device net vertex or connection All of the connections can be followed in constant time so navigating between n vertices requires O n operations Open and Closed Vertexes At a later stage in the project it became apparent that it would be necessary to draw a distinction between vertices that are open and those that are closed This terminology which is used in several papers 12 15 is used to distinguish between the vertices that can act as extension points for a circuit and the vertices that cannot An open vertex is a point in a circuit that may have anything added to it by a supercircuit of that circuit A closed vertex may not have anything added to it by any supercircuit Figure illustrates this with a simple example Key o Open Net Vertex x e o e Closed Net Vertex a b c Figure 3 3 All of the vertices in a are closed c cannot be a supercircuit of a because c makes an extension to a that is not permitted since the extension is made to a closed vertex However one vertex in b is open marked as x c is a supercircuit of b because it makes an extension to b at the open vertex z It is very important that the comparison algorithm recognises the difference between open and closed vertices because some apparent extensions to a
95. Mellon University Dept of Comput Sci 1981 M Frohlich and M Werner davinci an x window visualisation tool for drawing directed graphs automatically http www informatik uni bremen de daVinci M R Garey and D S Johnson Computers and Intractability A Guide to the Theory of NP Completeness W H Freeman amp Co 1990 G Jones A M Robertson C Santimetvirul and P Willett Non hierarchic document clus tering using a genetic algorithm http informationr net ir 1 1 paperi html F Luellau T Hoepken and E Barke A technology independent block extraction algorithm In 21st Proceedings of the Design Automation Conference on Design automation pages 610 615 IEEE Press 1984 J Morris Data structures and algorithms Red black trees http ciips ee uwa edu au morris Year2 PLDS210 red_black html D R Musser G J Derge and A Saini STL Tutorial and Reference Guide C Programming with the Standard Template Library Second Edition Addison Wesley 2001 M Ohlrich C Ebeling E Ginting and L Sather Subgemini identifying subcircuits using a fast subgraph isomorphism algorithm In Proceedings of the 30th international on Design automation conference pages 31 37 ACM Press 1993 E Pollard and H Liebeck editors The Oxford Paperback Dictionary 4th Ed Oxford University Press 1994 J Seward Valgrind http valgrind kde org R L Spickelmier and A R Newton Connectivity verification usin
96. OUT 80 Input 1 Output 5 VCC 7 SUBCKT INVERTER 1 5 7 Q1321N 02 4 3 10 N 03 645N Q4 8 100 N 5 7 DOSNDUIDSWNH 9 DI 8 DIODEM 10 Ri 2 4K 11 R2 47 1 6K 12 R3 10 0 1K 13 R4 6 7 130 14 ENDS INVERTER 15 MODEL DIODEM D 16 MODEL N NPN BF 75 RB 100 CJE 1PF CJC 3PF 17 X1 100 200 300 INVERTER 18 VCC 300 0 DC 5 19 END Figure 3 2 The SPICE circuit description for the circuit illustrated in Figure In Figure the lines beginning Q R D and X describe four types of electronic device they are element cards The lines beginning are comments as is the first line the title The lines beginning with a are control cards Many of these can be safely ignored giving hints to the SPICE interpreter that do not affect the structure of the circuit The ones that cannot be ignored are the MODEL SUBCKT and END control cards Most element cards translate directly to device vertices The only exception is the SPICE subcircuit element denoted by the SUBCKT card Subcircuit elements are analogous to procedure calls Each subcircuit element is replaced with all the elements that make up the subcircuit Here the subcircuit element X1 on line 17 is replaced with all the elements in the INVERTER subcircuit lines 5 to 13 As can be seen in Figure no trace of X1 remains when the complete circuit is drawn out The MODEL control card describes the parameters used to model devices such as diodes and transistors The parameters are
97. Relabeller dev subgraph partition copy NULL Ohlrich Circuit Exclude If Matched true net graph partition copy this gt net partition Relabeller net graph partition copy NULL Ohlrich Circuit Exclude If Matched true 880 dev graph partition copy this gt dev partition Relabeller dev graph partition copy NULL Ohlrich Circuit Exclude If Matched true if net subgraph partition copy empty amp amp dev subgraph partition copy empty debug All verticesymatched n Build_Match_Record that mc 890 if only find one match Back_0ut_Relabelling NULL amp change_list return mc else debug A11 connected vertices matched but Xdynetypartitionsjandu 4dyudevypartitionsjremain Nn net_subgraph_partition_copy size dev_subgraph_partition_copy size 900 H So if there IS anything left to match if equiv class check failed amp amp net subgraph partition copy empty amp amp dev subgraph partition copy empty 910 Reset flags on all unmatched vertices Reset_Flags net_subgraph_partition_copy NO_CHANGE Reset_Flags net_graph_partition_copy NO_CHANGE Reset_Flags dev_subgraph_partition_copy NO_CHANGE Reset_Flags dev_graph_partition_copy NO_CHANGE Out of net_subgraph_partition_copy and dev_subgraph_partition_copy choose the smaller but non
98. Search procedure 1000 times finding all circuits in the database that match X The amount of CPU time required for this is measured by the times function which is a part of the system C library times measures the number of units of processing time used directly by the program excluding any used by other programs On the test system a unit of processing time corresponds to 10 milliseconds of real time Since searches often take much less time than this it is essential to run the Search procedure many times in order to get an accurate timing for one execution The number of ticks is multiplied by 10 milliseconds and divided by 1000 to obtain the amount of time taken for each search Up to 27 circuits may be examined during each search because the database contains all the circuits in the test corpus described earlier The timings that were obtained for each circuit and each search type are shown in Figure The mean time taken by a search is 15 6 milliseconds The standard deviation is 10 0 milliseconds indicating that about 84 of all searches will take less than 25 6 millisecond This is clearly fast enough for the search algorithm to be used interactively Basic Schmitt p40 cl PZ i i i Hex inverters p30 cl pzzzzzzzzza i i i Generic High Speed p10 cl Pp FAAA i STM Search Cerat Search Hex inverter p38 cl HA i Hex inverter p16 cl EZ EALA SN74S04 Schematic p24 cl pzzzezzegezzzeszizzzzzzz4za Two input NAND gate p28 c1
99. Write out for Circuit Number i t rc rc amp amp db i amp amp Serialisable Int amp amp Serialisable Int amp amp Write Unsigned Map amp amp Write Unsigned Map return rc Serialisable_Int if ready sz 0 i lt db_size i cr db i db i out out magic Write out D throw database already built super to sub order sub to super order db i supers db i subs Read std ifstream amp in sub to super order Project Source Code Write out Write out super_to_sub_order 123 libcrdb src database cc if magic Read in amp amp sz Read in return false 290 if magic Get MAGIC_NUMBER_2 return false db size sz Get db new Database Record db size for Circuit Number i 0 i lt db_size i 300 1 if db i cr Read in amp amp super to sub order Read in amp amp sub to super order Read in amp amp Read Unsigned Map in db i supers amp amp Read Unsigned Map in db i subs db i super_to_sub_order super_to_sub_order Get db i sub_to_super_order sub_to_super_order Get else 310 delete db return false ready true return true 320 debugging functions 330 void
100. _x lambda 90 else score pow value x value_y lambda match_records back score score double Scored_Circuit Get_Value Device_Vertex v 100 if v gt type RESISTOR amp amp v gt type CAPACITOR amp amp v gt type INDUCTOR the value cannot be used return 1 0 const char x value str v gt model c str 110 size t value len strlen value_str double exponent 1 0 size t d bool done false The value information is in value str which is now decoded for i 0 i lt value len i switch toupper value_str i 120 1 case T tera exponent 1E12 done true break case G giga exponent 1E9 done true break case M could be one of a few things 130 if strcasecmp amp value_str i MEG 0 mega exponent 1E6 else if strcasecmp amp value_str i MIL 0 Project Source Code 140 160 170 180 190 10 libcrdb src serialisable cc 160 mil as in 1 1000 inch exponent 0 0000254 else milli exponent 1E 3 done true break case K kilo exponent 1E3 done true break case U micro exponent 1E 6 done true break case N nano exponent 1E 9 done true break case P
101. a particular type of substructure within them such as an output stage Feature 3 is very useful provided that the database contains suitable fragments It will allow a user to identify all of the fragments that are present in their circuit Fragments might include such things as Darlington pairs input stages output stages flip flops and Schmitt triggers all of which are important components in certain types of circuit but which may not be readily identifiable The search tool will be able to provide a list of them all However all the features rely on the database having suitable content Feature 3 requires the database to contain circuit fragments and the others require it to contain complete circuits Of Chapter 7 Evaluation 61 course these are not mutually exclusive in fact it is beneficial to have both because it allows the search algorithm to eliminate a larger proportion of the search space The corpus of circuits that was used for testing contained some fragments and some complete circuits Not only must the database have suitable content but that content must be annotated in a suitable manner All of the circuits in the database should have annotations that describe their function which should be displayed after searching is complete if the user so desires Without this the output of the search tool will not be particularly useful for learning about circuits since nothing will be taught The annotations can be used to pro
102. aightforward to extend it A second class Luellau Circuit was written l his added a Compare To function which compares one circuit with another using Luellau s algorithm This returns TRUE if one circuit is an isomorphic subgraph of the other and FALSE otherwise 3 2 2 Operation of the Algorithm Luellau s algorithm works in three phases The first phase finds suitable starting points within the smaller of the two circuits by attempting to find a net or device vertex with a maximal number of unique edges A unique edge of a vertex is one that can be distinguished from all the other edges because it is connected to a type of device that no other edges are connected to Once a suitable starting point is found the set of vertices that are equivalent to it in the larger circuit are found One is selected as a match This is the non deterministic phase of the algorithm because there may be more than one possible equivalent vertex The algorithm may pick the wrong one and be forced to backtrack The third phase of the algorithm is deterministic It is a gradual process in which items in the smaller graph are matched to items in the larger graph Two items are only matched if the algorithm can be certain that they are equivalent Provided that the correct match was made in the second phase the matches made here will all be correct Figure 3 4 illustrates this phase In the example shown eight iterations of the third phase are required to matc
103. ajdatabase builder for the circuit repository Nn Nn Usage build db database file name circuit list file Mn Mn The database file jis destroyed ifjitjalready jexists n The circuitylist file should be a plain textfile with the n complete path and file name jofja SPICE circuitjonjeach line n The listed circuits are yadded to the database In return 1 printf Loading circuits from s n argv 2 fd fopen argv 2 rt if f NULL perror openingucircuitulistufile return 1 rc CR_Create_Handle amp handle 91 60 TO 80 90 100 110 120 apps dump_db c 92 if rc CR_OK printf CR_Create_Handleyfailed 4s n CR_Get_Error_String rc return 1 rc CR_Create_Database amp handle if rc CR_OK printf CR_Create_Database failed s n CR_Get_Error_String rc return 1 while feof fd char circuit file 256 fgets circuit file sizeof circuit file 1 fd Remove NL circuit file if strlen circuit file 0 feof t continue rc CR Add Circuit amp handle circuit file if rc CR OK printf CR_Add_Circuit failed when adding circuit from s n t s n circuit file CR Get Error String rc return 1 count printf r d circuitsyloaded co
104. al Order db size 1 0 Item 0 in the circuit array is the empty circuit Item db size 1 is the universal circuit assert db 0 cr Is Special assert db db_size 1 cr Is Special ready true void Database Add_Circuit Serialisable_Circuit_Record c f ready i throw database_already_built c ircuit_list push_back c void Database Search Serialisable Circuit Record amp for this Search Flags sf Search Result List amp results To Be Checked Queue to be checked To Be Checked Queue Type queue type Circuit Hash Map known Circuit Hash Map examined Edge Degree degree 0 bool ok false Circuit Map iterator iter2 Match Record List mrl Search Result Map results map Search Type st sf search type bool find_eguivalents false Search_Result_Map iterator rmi f ready Lt mo throw database not built results clear results map clear switch st case SEARCH_FOR_EQUIVALENT To find an equivalent circuit we search for a subcircuit of for_this and then refine the results to only include circuits that are also supercircuits of for_this find_equivalents true st SEARCH_FOR_SUBCIRCUIT fall through case SEARCH_FOR_SUBCIRCUIT Find all subcircuits of for_this in the database queue_type SUB_TO_SUPER to_
105. al bool Write std ofstream amp out const return true virtual bool Read std ifstream amp in return true virtual void Debug void const struct Unsigned Map std map lt unsigned unsigned gt Project Source Code 30 10 20 30 40 libcrdb include serialisable circuit record h 108 protected virtual bool Write Integer std ofstream amp out unsigned x const virtual bool Read Integer std ifstream amp in unsigned amp x const virtual bool Write Magic std ofstream amp out const virtual bool Read Magic std ifstream amp in const bool Write Unsigned Map std ofstream amp out Unsigned Map amp map const bool Read Unsigned Map std ifstream amp in Unsigned Map amp map const y namespace std Hendif D 14 libcrdb include serialisable circuit record h ifndef SERIALISABLE_CIRCUIT_RECORD_H define SERIALISABLE_CIRCUIT_RECORD_H include include include include include include include include include include serialisable_string h serialisable_int h serialisable_map h serialisable_set h serialisable_signature h circuit_manager h spice_interpreter h match_record h lt string gt lt ext hash_map gt namespace std class Serialisable_Circuit_Record public Serialisable public type definitions enum SCR Special SPECIAL EMPTY SPECIAL UNIVERSAL
106. al labelling to them This feature would result in a speed increase during every search This was done to some extent The SPICE Interpreter class was made serialisable so that once a circuit had been loaded in from a SPICE file it could be serialised into the database file and read back Serialisation is a much faster way to load a circuit than interpreting the SPICE file because there is no need to decode subcircuits and model information The data is read directly into the appropriate data structures However Section 4 3 also suggested that the serialised version of the circuit might be ready for use by Ohlrich s algorithm All vertices would be labelled beforehand and sorted into partitions Unfortunately it was found that this would require a major rewrite of the class that managed Ohlrich s algorithm since the labelling process is an integral part of every comparison To use serialised data would require a substantial architectural change and this was not feasible in the time available Despite this serialising the circuit does mean that searches will be much faster than they would otherwise be Implementing the circuit serialisation feature also means that there is no need to keep the original circuit files once the database has been built Those files do not need to be present and in the correct place during every search which will make things more convenient for any programmer making use of the circuit repository software Chapter
107. al time would constitute proof that P NP 3 It is possible to translate any general subgraph isomorphism problem X into a circuit com parison problem Y that can be solved by Luellau s algorithm e Every node in X must become a net vertex in Y e Every edge in X must become a resistor or any other component with two unordered connections So an edge connecting graph nodes a and b becomes a resistor linking net vertices a and b This translation can be done in linear time 4 If Luellau s algorithm always completed in polynomial time then it would be possible to use it to solve the general subgraph isomorphism problem in polynomial time by translating a general instance of the problem into a circuit 3 Since the problem is in NP 1 this would constitute proof that P NP 2 So provided that P NP Luellau s algorithm will take exponential time to complete in the worst case However experimentation with the algorithm suggests that the worst case is most unlikely to occur in any real circuit This was found by the authors of the algorithm who stated that the runtime increases almost linearly with the number of devices This is because restrictions can be placed on the types of match that are possible For example there are two types of vertex which can only connect directly to vertices of the other type And one type of vertex device vertices has a defined number of external connections and can only be matched to a part
108. alidate_Handle db if rc CR_0K return rc try ptr db gt Build catch const char ex 110 return Translate_Exception ex return CR OK Database disk I 0 CR_Error_Code CR_Load_Database CR_Handle db const char db_file CR_Error_Code rc CR_Create_Database db 120 if rc CR_OK return rc try ifstream fd db_file if ptr db Read d return CR_FILE_FORMAT_ERROR 130 catch const char ex return Translate_Exception ex return CR OK 140 CR_Error_Code CR_Save_Database CR_Handle db const char db_file Project Source Code 183 src interface cc CR_Error_Code rc Validate_Handle db if rc CR_OK return rc try ofstream fd db_file 150 if ptr db Write fd return CR_WRITE_FAILED catch const char ex return Translate_Exception ex return CR_OK 160 Database searches CR_Error_Code CR_Find CR_Handle db CR_Search_Flags sf const char c file CR Result List r r OL CR_Error_Code rc Validate_Handle db if rc CR_OK 170 1 return rc if r OL s 0L return CR_NULL_POINTER 180 Database Search Flags db_sf Database Search Result List db results CR Search Type st sf gt type Convert search type from CR Search Type to Search Ty
109. andard output using a simple format that describes each circuit in the part of graph on a single line Each line lists the name of the circuit and the contents of the supercircuit set and the subcircuit set 49 50 A Graph Matching Search Algorithm for an Electronic Circuit Repository The output of the Debug procedure requires some substantial processing before it can be read in by daVinci daVinci graphs are described by a unique graph description language and the output of Debug is translated to this format by a Perl script written by the author named by db to davinci pl Then graphs can be visualised in daVinci Figure 7 1 illustrates a part of graph that has been drawn using ten circuits from the test corpus A larger part of graph containing all of the circuits in the test corpus appears in Figure at the end of this chapter _empty circuit_ 0 inf inf inf inf Hex inverter SN74S04 Schematic i Hex inverters 16 ct 1 p24 c1 1 m p30 c1 1 2 2 2 inf 1 y Y y Y 2 input NAND 2 input NOR 2 input NAND T gate p12 c1 gate p14 c1 gate p22 c1 DER s 2 2 2 2 int inf 2 Y Generic Standard Two input NAND NAND p8 c1 gate p28 c1 3 3 inf inf _universal circuit_ 4 daVinci V2 1 Figure 7 1 The part of graph for a database containing ten circuits from the test corp
110. ant time list h 98 finclude lt string gt include lt assert h gt namespace std class Circuit_Manager public Serialisable public Circuit Manager const std string amp location Circuit Manager virtual Circuit Manager std string Get_Circuit_Name void const return circuit gt Get Circuit Name Serialisable_Signature Get_Circuit_Signature void const return circuit gt Get Circuit Signature D bool Contains Closed Net Vertices void const return circuit gt Contains Closed Net Vertices bool Test Connectedness string amp o return circuit Test Connectedness o int Is Subcircuit Circuit Manager amp sub std Match Record List amp mrl bool assume all vertices are open bool only find one match bool sort by size D D bool Write ofstream out const return circuit gt Write out bool Read ifstream amp in return circuit gt Read in void Debug void const return circuit Debug private Std Scored Circuit x circuit copy assign not allowed D Circuit Manager const Circuit Manager amp assert 0 Circuit Manager amp operator const Circuit Manager amp assert Fa namespace std Hendif D 6 libcrdb include constant_time list h ifndef CONSTANT_TIME_LIST_H define
111. any link between A and B that is indirect i e connects the two via one or more intermediate items If no such link is found return to step iii Remove the edge between A and B subsp subsp A and supersa supersA B In this algorithm step 1 a ii may be optimised by starting the search at the children of node A and recursing through the graph from subcircuits to supercircuits This is guaranteed to find the link because B is a supercircuit of A and cannot therefore be closer to the empty circuit than A It is also guaranteed to complete because no cycles exist in the graph Chapter 5 Development of an Optimised Search Method 37 5 5 5 A search algorithm for finding subcircuits using a part of graph In this section the search algorithm that makes use of the part of graph will be described The description of the algorithm assumes that the user wishes to find all the subcircuits of some circuit X in the database The algorithm for finding all supercircuits of X is very similar as will be discussed later Firstly suppose that the part of graph for a set of circuits has been determined by the processes described earlier This means that for each circuit X a set of supercircuits a set of subcircuits and a topological order are available The algorithm for finding all subcircuits of a circuit X using the database is as follows 1 Let known and examined be sets of database circuits both initially empty 2 Let to be che
112. artition Verify Image Core dev subgraph partition copy 830 dev graph partition copy amp change list equiv class check failed progress else debug Iteration d nets n iterations net graph partition copy this gt net partition net subgraph partition copy that gt net partition 840 Verify Image Core net subgraph partition copy net graph partition copy amp change list equiv class check failed progress Project Source Code 153 libcrdb src ohlrich circuit cc doing_devs doing_devs while equiv_class_check_failed amp amp progress 850 progress_last_time There was no progress on the last iteration How many unmatched vertices remain if equiv_class_check_failed debug Equivalence class check failed n else if net_subgraph_partition_copy empty amp amp dev_subgraph_partition_copy empty 860 Unfortunately this does not mean that we have finished matching the circuit because it may not be connected We could assume that the circuit is always connected and just return true here but that wouldn t be great debug All connected verticesymatched n net_subgraph_partition_copy that gt net_partition Relabeller net_subgraph_partition_copy NULL 870 Ohlrich_Circuit Exclude_If_Matched true dev_subgraph_partition_copy that gt dev_partition
113. ase pi graph partition copy erase weight else if srsize rsize Equal sized partitions with the same weight debug Anjegualysizedupartitionuwithutheu same label d was detected 1n weight Vertex_List_Iter i 1210 for i super_region begin i super_region end i if x i gt safe Save Item On Change List change list x i AssignedAndSafe x i gt safe true progress true 1220 for i region begin i region end i if x i gt safe Save Item On Change List change list x i AssignedAndSafe x i gt safe true Project Source Code libcrdb src scored circuit cc 158 1230 progress true pi else Next item no erasure pi D 27 libcrdb src scored_circuit cc include scored_circuit h using namespace std Scored_Circuit Scored_Circuit 10 int Scored_Circuit Compare_To Scored_Circuit kt Match Record List amp mrl bool assume_all_open bool only find one match bool sort by size int ret code hlrich Circuit Compare To t mrl 20 assume all open only find one match size t num matches mrl size f num matches lt 2 no need for sorting return ret code sort matches first convert the Match_Record_List to an array because sorting a linked list directly will be
114. ase disk I 0 CR EXT CR Error Code CR EXT CR Error Code Database searches CR EXT CR Error Code const char x Deallocation CR EXT CR Error Code Debugging get a CR EXT CR Error Code Error codes CR Create Database CR Find CR Handle x db CR Free Result List CR Handle db CR Handle db CR Handle db CR Build CR Handle db CR Load Database CR Handle x db CR Save Database CR Handle db c file 25 const char c_file const char db file const char db file CR Search Flags sf CR Result List r CR Result List r dump of the database contents on standard output CR_Debug CR Handle db CR_EXT const char CR Get Error String CR Error Code c Hendif D 5 production of a filename name for each circuit A XA AO X X X XX ifndef CIRCUIT_MANAGER_H define CIRCUIT_MANAGER_H include serialisable int h include serialisable map h P include serialisable signature h g include scored circuit h include match record i lud h d h libcrdb include circuit manager h The job of this module is to provide a signature map for Serialisable_Circuit_Record with the property that comparison can be done with Is Signature Subset comparison feature for circuits Project Source Code generated on deg DES 30 40 60 70 10 libcrdb include const
115. ation cr_record cr_record gt next delete last catch return CR_NULL_POINTER 350 return CR OK CR Error Code CR Free Handle CR Handle x db CR_Error_Code rc Validate_Handle db false if rc CR_OK return rc 360 if ptr db OL delete ptr db ptr db OL mag db OL delete _CR_Handle db db OL return CR OK 370 const char CR_Get_Error_String CR_Error_Code c Project Source Code 380 390 400 410 420 430 440 src interface cc 186 define MESSAGE code str V case code V return code str switch c MESSAGE CR OK No error MESSAGE CR_FILE_NOT_FOUND The specified file was not found MESSAGE CR OUT OF MEMORY A memory allocation operation failed MESSAGE CR NO DATABASE The database does notu exist Mn itymustpeitherubejbuiltyorjloadedufromjaufile Nn You need to call either CR_Load_Database or CR_Build MESSAGE CR INVALID HANDLE The CR Handle supplied was invalid MESSAGE CR DATABASE HAS ALREADY BEEN BUILT The database hasLalready beenybuilt n Once the database is built it is finalised and cannotWYn be added to or rebuilt MESSAGE CR DATABASE ALREADY EXISTS The database has already been created and cannot therefore n be loaded from disk or recreated Create a new handle
116. ause the time complexity of the operation is at least linear in the size of the hash table and not linear in the number of items in the table as might be expected The size of the table may be much larger than the number of items in it indeed it is usually a good idea to ensure that a hash table is as large as reasonably possible A comment that appears in hash c indicates that the developers of the original implementation changed their minds about the use of hash tables This whole hash table stuff was probably a mistake in the false assumption that there 25 26 A Graph Matching Search Algorithm for an Electronic Circuit Repository were going to be a lot of partitions Since there are usually not we can just use linked lists or something like that The author of this comment is correct the use of a hash table to store vertex data was a mistake However the solution proposed linked lists is no better because the algorithm requires more than simple iteration through each set of vertex data It also requires random access There are some operations which require vertices with particular labels to be found such as test equivalence classes in which the labels present in the smaller circuit are checked against those in the larger circuit A red black tree 13 is a much better choice of data structure A red black tree is a balanced binary tree with the property that the search for a node will take O log n operations if th
117. be in SPICE format It then searches the database associated with the given handle for instances of either subcircuits or supercircuits of it depending on the setting of the CR Search Flags parameter CR Search Flags is a structure defined as follows typedef struct CR Search Flags struct 1 CR Search Type type BOOL dont assume open BOOL only find first match BOOL sort by match size CR Search Flags Here the type field indicates the type of search that should be carried out The available types are e CR SEARCH FOR SUBCIRCUIT subcircuits of c file are found e CR SEARCH FOR SUPERCIRCUIT supercircuits of c file are found e CR SEARCH FOR EQUIVALENT the isomorphic circuits of c file are found The dont assume open field indicates whether or not all vertices should be considered to be open If set to TRUE the true status of each vertex open or closed is always used If set to FALSE the subcircuit vertices are assumed to be open The only find first match field indicates whether or not more than one match is required If TRUE then the matching process will stop after the first complete match is found for each circuit the match results produced will contain one match per circuit T his is always faster than searching for all matches The sort by match size field is a parameter of the method used to sort results If it is TRUE then results are sorted in order of the number of vertexes that matched within th
118. be_checked push To_Be_Checked_Entry queue type 0 break case SEARCH_FOR_SUPERCIRCUIT Find all supercircuits queue type SUPER TO SUB to be checked push To Be Checked Entry queue type db size 1 break default assert 0 break while to_be_checked empty Project Source Code libcrdb src database cc 126 Get the next item off the gueue Circuit_Number current to_be_checked top second Serialisable Circuit Record amp c db current cr to be checked pop 520 Have we seen this one before It is possible for one circuit to be put on the queue several times if examined count current 0 continue examined current 1 530 ok true Now check that all sub supercircuits of c are present in the reguired numbers switch st case SEARCH_FOR_SUBCIRCUIT for iter2 db current subs begin iter2 db current subs end iter2 540 Circuit Number circuit iter2 first Edge Degree degree iter2 second if known count circuit 0 sf only find first match amp amp known circuit degree ok false break 550 break case SEARCH_FOR_SUPERCIRCUIT for iter2 db current supers begin iter2 db current supers end iter2 Circuit Number circuit iter2 first Edge De
119. cause of their efficiency Insertions and removals from a binary heap take place in O log n time If a red black tree were used in place of a binary heap it would have the same time complexity However it would be slower in practice because of the complex nature of the code that maintains the balance of the tree The code that keeps a binary heap in priority order is very simple in comparison and since there is no need to access any item in the binary heap apart from the one at the front there is no need to use a red black tree 5 6 2 The shape of the part of graph The performance of the algorithm depends on the shape of the part of graph If every circuit in the graph had only one subcircuit the empty circuit and one supercircuit the universal circuit then the algorithm would still work But it would be no better than examining every circuit in the database This scenario would occur if none of the circuits in the database was a subcircuit of any other a situation which is quite possible Any type of circuit may be added to the database The ideal part of graph would have as many levels as possible so that length of the shortest path from the empty circuit to the universal circuit is maximised This provides the search tool with a structure to work from If the database tools were able to assure that the part of graph would have this ideal shape then the user could be certain that the search tool would work quickly with any circuit that m
120. ccurrences of a particular circuit in X or the number of occurrences of X in a particular circuit for comparison with the degree value Chapter 5 Development of an Optimised Search Method 41 5 7 Implementation The algorithms discussed in this chapter were implemented in a new class called Database 5 7 1 Serialisation While writing this class the author was aware that the database would need to be stored on disk To this end a feature of the Java programming language called serialisation was borrowed Serialisation is a process whereby all of the information stored in an object is written to a stream generally a file It is a recursive operation when an object is serialised all of the objects that it contains are also serialised in some order that is defined by the object The process is called serialisation because an object ceases to have a structure in the machine s memory It becomes a flat stream of information in which each sub object comes immediately after the previous one in series It is however a reversible process The stream can be restored to produce an eguivalent structure in the computer s memory although the actual locations of each object may be different In Java serialisation is a primary language feature It is provided by the interpreter and any class that implements an interface called Serializable can be serialised The great advantage of serialisation is that a class can have the ability to be written
121. ce Code libcrdb src spice_interpreter cc 176 nli that master net list end nli assert nli gt assigned m net matches push front pair lt int int nli number nli gt matches gt number match records push back m 630 bool Spice Interpreter Contains Closed Net Vertices void const Net Vertex List const iterator nli for nli master net list begin nli master net list end nli if x nli open 640 return true return false serialise the SPICE circuit bool Spice Interpreter Write std ofstream amp out const 650 map lt Net_Vertex unsigned nets Device Vertex List Iter const iterator dli Net Vertex List Iter const iterator nii unsigned serial number 1 bool rc true build net pointer to number translation map for nli master net list begin nli master net list end nli 660 nets nli serial number serial number rc rc amp amp Serialisable String circuit name Write out serialise device list rc rc amp amp Write Integer out master device list size for dli master device list begin dli master device list end dli 670 Device Vertex Connection Map amp dvcm dli gt connections rc rc amp amp x dli gt model Write out
122. cent to two capacitors 2 4 Research into Circuit Matching In the following section the efforts of various researchers to find algorithms for circuit comparison wil be examined As will be seen not all of the researchers made use of graph or subgraph isomorphism techniques However it will become clear that such techniques are an essential part of general circuit comparison 8 A Graph Matching Search Algorithm for an Electronic Circuit Repository 2 4 1 The Work of Ablasser and J ger 1981 Ablasser I describes a method to compare mask artwork with the original circuit diagram The production of a mask is an intermediate step in the production of an integrated circuit on silicon analogous to the production of a photographic plate in conventional printing At the time of Ablasser s research mask production was only partially automated and human errors were occasionally but inevitably introduced These errors might result in expensive hardware faults especially if many integrated circuits had been manufactured before the fault was found So manufacturers needed to find a way to verify masks before they were used in production Ablasser s program does this by checking the circuit topology how the various components are connected Ablasser developed a technology independent method of circuit comparison based only on the circuit structure The method can only detect graph isomorphism it is not able to tell if one circuit is a subcircuit o
123. ches However interesting techniques have been described such as functional isomorphism It may be possible to find circuits with a different structure but the same function by making use of functional isomorphism algorithms Some research 12 15 has been done into adapting the methods described earlier to find a subcircuit within a larger circuit This research will now be examined As will be seen it is directly relevant to the problem to be solved in this project 2 4 5 The Work of Luellau 1984 A paper by Luellau 12 describes a program called BLEX a program to find instances of a functional block within a circuit This is similar to the reduction technique applied by Takashima where a particular arrangement of transistors was identified as a particular logic gate However while Takashima s technique was hardwired with information about what to look for Luellau s technique is general The functional block may be any user provided circuit of any size Luellau suggested that his program might be used to extract logic gates and larger components from a circuit described at the transistor level But this is only one use of the technique It can also be used to find a general subcircuit within a general circuit and even to compare two circuits of the same size The algorithm for subgraph isomorphism described by Luellau of particular interest The algo rithm described by Ablasser is used but with an improvement instead of label
124. child db sub_number supers end child if child first super_number return true Search for indirect links 100 for child db sub number supers begin child db sub number supers end child if Is_Link_Between child first super_number return true return false void Database Remove_Transitive_Links Circuit_Number sub_number Circuit_Number super_number 110 Only the longest link between the two circuits must remain First we require that a there is a link between the two b super_number is a supercircuit of sub_number 120 if db sub_number supers count super number 0 return assert db super_number subs count sub number 0 bool longer link found false Circuit Map iterator child 130 Now is there a longer link than this one This is a tree search Project Source Code 121 libcrdb src database cc with sub number at the root We start with the children of sub number we have to otherwise we will just find the direct link for child db sub number supers begin child db sub number supers end child if Is_Link_Between child first super_number 140 longer_link_found true break f longer_link_found O me Yes there is a longer link Destroy this
125. cked be a priority queue of database circuits in which the topological order of each circuit determines its position in the queue The circuit with the lowest topological order in the queue will always be at the front 3 Push the empty circuit onto the queue 4 Repeat until the queue is empty a Let Y be the item at the front of to be checked b Remove Y from to be checked c If Y examined then return to step da re m d Add Y to the examined set e PA CTS Apply trivial tests to see if Y could be a subcircuit of X such as those described in Section 5 3 If they fail return to step f For each W subsy do i Check that W is present in the known set If it is not then Y cannot be a subcircuit of X go to step g Apply Ohlrich s algorithm to test if Y is a subcircuit of X If it is not then go to step dal h Add Y to the Known set i Add all supercircuits of Y supersy to the to be checked queue On completion of the algorithm the known set contains all of the circuits in the database that are subcircuits of X The algorithm operates in an iterative fashion starting at the empty circuit On finding that some circuit Y is a subcircuit of X all of the supercircuits of Y are added to to be checked the queue They will be examined in later iterations Since a part of graph has been precomputed the set of supercircuits of Y is known If Y is not present in X then any and all superc
126. ct Source Code 320 330 340 360 370 380 390 libcrdb src spice interpreter cc 172 device gt model string else device gt model string line Just for debugging device gt name string name Add the device to the master list used for deleting them master_device_list push_front device void Spice_Interpreter Read_Model char line Spice_Model_Name name string type_str Type type UNKNOWN char x 1 line Make the string all capitals for comparison purposes while 1 0 NO 1 0 toupper 1 0 1 debug Readumodel u sNn line void Get_Word amp line Remove first word MODEL name Get_Word amp line 2nd word model name type_str Get Word amp line 3rd word model type debug nameu u s utypeuru s Nn name c_str type_str c str if type_str compare 0 3 NPN 0 type NPN else i type_str compare 1 if YP p 0 3 PNP 0 type PNP else i type_str compare 1 if YP p 0 3 NJF 0 type NJFET else i type_str compare 1 if YP p 0 3 PJF 0 type PJFET else i type_str compare j mE 1 if YP p 0 4 NMOS 0 type NMOS else i type_str compare M A 1 if YP p 0 4 PMOS 0 type PMOS if type UNKNOWN Spice models name type i void Spice
127. ction 3 A simple heuristic such as checking if the two circuits have the same numbers of components in them would not make a useful comparison Many circuits have similar sets of components An algorithm is needed that is capable of comparing the structure of the circuits However this type of comparison heuristic may be useful as a way to cut down the size of the search space by eliminating circuits that cannot possibly be matched Fortunately there is a solution to the comparison problem from graph theory A circuit may be treated as a graph Although graphs are commonly thought of as a plot of a function or statistical data a graph is also a general term for a collection of vertices linked by some connections known as edges Equivalent circuits have identical components connected identically and if those circuits are treated as graphs existing graph comparison algorithms can be used to compare them Some data structures seen in the field of Computer Science are special types of graph For example a tree is a type of graph one in which there are no loops an acyclic graph and all vertices are either connected directly to the root or connected to the root via some other vertices The electronic circuit is no exception A circuit may be represented as a graph in various ways one of which is illustrated in F igure 1 1 a c O a C diode ve O ve 5 o d 3 bz 2 ve 5 5 dh ve diode a C Figure 1 1 T
128. cuit of B If it is not return to step 3a iii If B subsa then B is both a supercircuit and a subcircuit of A Therefore A and B are equivalent Return to step iv Add A to subsp v Add B to supers 4 Remove transitive edges 5 Calculate the topological order of each circuit starting with the empty circuit which will have topological order 0 using the algorithm outlined in Section 5 5 3 Detection of Equivalence As a side effect the algorithm is able to detect equivalence between any two circuits step 3 a iii Subcircuit is a reflexive relation a circuit is a subcircuit of itself So if two circuits are subcircuits of each other they must be isomorphic and therefore equivalent There is little point in putting equivalent circuits in the database If two circuits are equivalent they will always show up in a list of search results together Unless one circuit has two completely different uses it is unlikely that there would be any need for this However the algorithm handles equivalent circuits without difficulty It simply assumes that some ordering does exist between the circuits in an unspecified direction and continues This avoids any need to handle equivalent circuits as a special case However the user should be notified when equivalence is found since it may indicate that a circuit has been put into the database twice by mistake Remove Transitive Edges Step MA requires some explanation The algor
129. cuits clear spice_models clear void Spice_Interpreter Read_Device_Vertex char line Spice_Node_Map amp node_map 220 Spice_Component_Name name Get Word amp line device name Pin ext nodes 0 Type type UNKNOWN The first letter of the device name indicates the type of the device switch toupper name 0 1 230 case Q Bipolar junction transistor case J JFET type UNKNOWN type determined later ext nodes 3 break case M MOSFET type UNKNOWN Project Source Code 171 libcrdb src spice_interpreter cc ext_nodes 4 break case D type DIODE 240 ext_nodes 2 break case L type INDUCTOR ext_nodes 2 break case C type CAPACITOR ext nodes 2 break case R type RESISTOR ext nodes 2 250 break case T cerr lt lt nThe transmission line component type lt lt isynotysupported ysorry n throw file_format_error return case K cerr lt lt nThe mutual inductor component type lt lt isynotysupported sorry n throw file format error return case X a subcircuit must do something special 260 Read Subcircuit Device Vertex line node map return case G Voltage controlled current source case E Voltage controlled voltage source case F Current controlled current source
130. cuits used for testing purposes by writing a conversion tool that extracted the circuits from the Book Emulator e Dr Carl Ebeling at the University of Washington who provided the source code of the Sub Gemini implementation of Ohlrich s algorithm e Professor David Eppstein at the University of California Irvine who clarified the time com plexity of various types of graph isomorphism problem e Dr Alan Frisch at the University of York who made suggestions about matching circuits as a general constraint satisfaction problem e Dr Stefan Klinger who gave a lecture on molecular similarity searching using relaxation by elimination techniques as applied by the Advanced Computer Architectures Group to chemical graph matching The Group s work on this subject includes the paper by Turner and Austin 27 discussed in Section 8 3 Dr Klinger was also kind enough to provide a list of references on the subject e Dr Nick Pears who suggested the use of relaxation by elimination techniques as a way to carry out circuit matching e Jillian Wade who assisted with proofreading The source code of the circuit repository software is entirely the work of the author with two exceptions In ohlrich_circuit cc the random1 and random2 macros have been copied verbatim from the original SubGemini source code by Ohlrich and Ebeling along with the prime number table in the Get A Prime function This work was typeset using pdfTeX 3 14159 1 10b with f
131. d not present n weight Is it in the list of non unique edges 640 this Get Edges nv nvl_2 false if nvl_2 count weight Ex 0 no debug Comparison conflict edge of weight Ad Project Source Code 137 libcrdb src luellau circuit cc not present evenyinynon uniques n weight comparison_conflict true break 650 The bummer is that we have to make a choice between gt 1 candidates for later expansion That s no good Note we don t have a list of those candidates One of them is in nvl_2 weight but because that is a set keyed on weight the rest are not available debug Choice between gt i identical edgesyatynodey 4d u 660 postponed n nvp gt number continue ei nvl weight Device_Vertex dv ei gt dev Device_Vertex dvp eip gt dev if ei gt assigned 670 debug Lu Comparison conflict edgeyassigned n comparison_conflict true break if dv gt assigned amp amp dv gt matches dvp dvp gt matches dv dvp gt assigned device is already assigned to something else 680 debug uuComparisonuconflict jdev_jassigned Nn comparison_conflict true break debug uuWould likeytoLmatchydevicesu s uandy s n dvp gt name c_str dv gt name c_str Ca
132. d Subgraph Isomor phism Both of the preceding sections have focused on ways in which the search algorithm described in this project could be improved However there is an entirely different algorithm which has the potential to be more effective Turner and Austin 27 noted that the screening techniques used by search tools such as Daylight for chemical matching have a serious shortcoming Although the screening process is fast it must be followed by a comparison process using a subgraph isomorphism algorithm This comparison process is likely to be slow since the subgraph isomorphism problem is NP complete Screening has helped to reduce the number of comparisons that must be carried out but there is always the possibility that a database may contain large numbers of structures that pass the screening process but do not match Turner and Austin 26 propose a new approach based on probabilistic relaxation labelling Probabilistic relaxation brings a major advantage over the existing subgraph isomorphism algo rithms 28 because no fixed relation is created between any two vertices When two vertices are matched together the match takes the form of a probability that represents the likelihood that they are the same A vertex may be matched to several other vertices in this way As the probabilistic relaxation process continues the probabilities are updated by taking contextual information into account Eventually some matches have a probability
133. d remove it We have to change the weight so the Project Source Code libcrdb src ohlrich circuit cc 148 460 location of the vertex in the partition will change if p NULL amp amp p gt count vertex weight gt 0 Vertex List amp region x p vertex gt weight Vertex List Iter vli for vli region begin vli region end 470 1 if vli vertex region erase vli break else vli if region empty 480 p erase vertex gt weight Restore original values vertex gt weight change_item original_weight vertex gt border change_item original_open re add to partition with the restored weight 490 if p NULL p vertex gt weight push_front vertex if change_item type Everything break else fall through case AssignedAndSafe 500 the assigned and safe flags need to be backed out vertex gt assigned change_item original_assigned vertex gt safe change_item original_safe break default assert typeuwasuwrong break 510 bool Ohlrich_Circuit Remove_Border_Nodes Partition amp p Partition iterator pi Vertex_List_Iter vli bool empty true for pi p begin pi p end 520 1 Vertex List amp region pi second for vli region begi
134. d to find the optimal group of dummy circuits A genetic algorithm could be used to search for the best group of dummy circuits A popu lation of initially random individuals would be created within a search program The genes of each individual would describe several dummy circuits in some way These individuals would be cross bred repeatedly to produce new generations perhaps with some mutation step and at each generation the least fit individuals would be eliminated Fitness would be measured by how well the dummy circuits differentiated between the real circuits 8 1 2 Conclusion The generation of dummy circuits is a difficult problem that is really a project in its own right An approach based on document clustering would be effective in reducing the search space in some cases but a great deal of work would be required to implement and test the algorithm used to generate them And questions must be asked about the potential gain of doing so given that the dummy circuits provide no benefit to searches for supercircuits of a user provided circuit As illustrated by the histogram in Figure searches for a subcircuit of a user provided circuit often require fewer comparisons than searches for a supercircuit The searches that require the largest number of comparisons are all supercircuit searches and adding dummy circuits does nothing to address this The implementation and analysis of the effectiveness of a dummy circuit generator are
135. d_size i _Key new_item 60 if new item Read in return false insert end new_item return true y 70 void Debug std ofstream amp out const typedef typename std set lt _Key _Compare _Alloc gt const_iterator IV for IV i this gt begin i this end i i Debug ys 80 y namespace std Hendif D 19 libcrdb include serialisable signature h ifndef SERIALISABLE_SIGNATURE_H define SERIALISABLE_SIGNATURE_H include serialisable h include lt assert h gt namespace std 10 class Serialisable Signature public Serialisable public Serialisable_Signature unsigned n Serialisable_Signature number_of_types 0 Serialisable Signature const Serialisable Signature amp s number of types 0 Make Copy s virtual Serialisable Signature 20 virtual bool Write std ofstream amp out const virtual bool Read std ifstream amp in virtual void Debug void const virtual void Register Component unsigned type virtual bool Is_Subset const Serialisable Signature amp sub const Serialisable Signature amp operator const Serialisable Signature amp s Make Copy s return this 30 private Project Source Code 10 20 10 20 libcrdb include spice interpreter h 114 unsigned number_of_types unsigned x counter virt
136. db src luellau circuit cc 128 for rmi results map begin rmi results map end 5 Search_Result_Record amp sr rmi second Match_Record_List amp mrl sr match_record_list Serialisable_Circuit_Record amp c sr circuit if st SEARCH_FOR_SUPERCIRCUIT rematch count degree c Is_Subcircuit for_this false sf only_find_first_match sf sort_by_match_size else if c Contains_Closed_Net_Vertices rematch_count st SEARCH_FOR_SUBCIRCUIT degree for this Is_Subcircuit c false sf only_find_first_match sf sort_by_match_size else degree 1 if degree 0 remove it results map erase rmi else rmi Copy the results into the results list They will come out in key order so they will be sorted for rmi results_map begin rmi results_map j results push front rmi second D 25 libcrdb src luellau_circuit cc include luellau_circuit h using namespace std change to lt for slightly silly behaviour that matches the paper define LESSTHAN lt static const int DEV ASSIGNED 41 static const int NET_ASSIGNED 43 Luellau Circuit Luellau Circuit istream amp fd Spice Interpreter fd The circuit has been read in and all the data structures have been populated prepared false starting ne
137. deals with what Spickelmier calls transistor permutations where several entirely different arrangements of transistors provide exactly the same function This is common in digital logic implemented on metal oxide semiconductor MOS integrated circuits It may also be quite common in analogue circuits The main disadvantage of this method in the context of this project is that it requires a lot of functional isomorphism rules to be specified beforehand Unlike Ablasser s method and the ones that will be seen later it has to be taught the comparison rules Additionally a rule based inference system would be needed 2 4 3 The Work of Takashima et al 1988 Takashima 23 describes a system that extends the ideas of Spickelmier and Ablasser First it performs reduction on both circuits Low level components such as transistors are reduced where possible to the logic gates they make up This simplifies the network Next the reduced circuits are compared by graph isomorphism The algorithm used is from another paper by Takashima 24 and is similar to Ablasser s There is one difference components that do not match are passed to a rule based subsystem for comparison This sub system is able 10 A Graph Matching Search Algorithm for an Electronic Circuit Repository to detect if the components have the same function using a database of rules for functional iso morphism Components that have different structures can still
138. e 5 after the last use B 5 A note on error codes All of the functions provided by the circuit repository return an error code of type CR Error Code The error code indicates success or failure Table lists all the possible error codes and their meanings If you wish to report error codes to the user in plain English you may want to consider passing them to CR Get Error String page 87 which translates them into text along with a short explanation of the possible cause of each Chapter B C Interface Documentation 77 Error code Meaning CR_DATABASE_ALREADY_EXISTS The database has already been created and cannot therefore be loaded from disk or recreated Create a new han dle if you wish to start a new database CR DATABASE HAS ALREADY BEEN BUILT The database has already been built Once the database is built it is fi nalised and cannot be added to or re built CR_DATABASE HAS NOT BEEN BUILT The database has not been built yet You must build it before writing it to disk or searching it CR_FILE_FORMAT_ERROR The format of a file on disk is incorrect CR FILE NOT FOUND The specified file was not found CR INVALID HANDLE The CR Handle supplied was invalid CR NO DATABASE The database does not exist it must ei ther be built or loaded from a file You need to call either CR Load Database page 88 or CR Build page B1 CR NULL POINTER A null pointer was given as a parame ter CR OK No error CR OUT
139. e 2 emitter case 0 return 11 case 1 return 13 940 case 2 return 3 break case PNP switch p case 0 return 5 case 1 return 17 case 2 return 7 j break 950 The following were not supported by Luellau s algorithm as originally described case INDUCTOR return 37 Project Source Code libcrdb src ohlrich circuit cc case NJFET switch p 1 case 0 return 47 case 1 return 53 case 2 return 59 break 960 case PJFET switch p case 0 return 61 case 1 return 67 case 2 return 71 break case PMOS switch p 1 case 0 return 73 970 case 1 return 79 case 2 return 83 case 3 return 89 break case NMOS switch p 1 case 0 return 97 case 1 return 101 case 2 return 103 980 case 3 return 107 break case UNKNOWN break note prime numbers 41 and 43 are reserved for ASSIGNED flags assert Unrecognised pin type return 1 990 bool Luellau Circuit Verify Assigned Net Vertices Device Vertex dvp Device Vertex dv 1 Device Vertex Connection Map Iter cmi __gnu_cxx hash_set lt int gt connected_to Make a set called connected_to of all the things that subcircuit device dvp is definitely connected to 1000 for cmi dvp gt connections begin cmi dvp gt connections end cmi Net Vertex x nvp cmi second if nvp assigned connected to insert int nvp ma
140. e Record change item 730 change item original weight v gt weight change item original open v border change item original assigned v gt assigned change item original safe v gt safe change item type t change item vertex v change item timecode counter change_list gt push front change item J 740 void Ohlrich_Circuit Match Vertex a Vertex b match weight a weight b gt weight positive rand a gt assigned b gt assigned true a gt safe b gt safe true assert a is net b gt is net if a is_net 750 debug Matchingunetu dutounetu d uwtu dSn Net_Vertex a gt number Net_Vertex b gt number a weight Net_Vertex x a gt matches Net Vertex b Wet_Vertex b gt matches Net Vertex a else debug Matchingudevice_u sutoudeviceu s uwtu dSn Device Vertex x a name c str 760 Device Vertex x b name c_str a weight Device Vertex a gt matches Device Vertex b Device Vertex b gt matches Device Vertex a Project Source Code libcrdb src ohlrich circuit cc 152 phase 2 770 int Ohlrich Circuit Verify Image Vertex keynode Vertex List amp candidate vector Vertex List Iter vli int mc
141. e in common is that there exists a graph S that is both isomorphic to 5 and a subgraph of G This is formally expressed in equations 2 2Jand 2 3 The first equation states that S is isomorphic to S The second states that S is a subgraph of G Vu Vs va Vs 01 02 Es gt f v1 f v2 Es 2 2 Vv Vy v2 Vy vi v2 Es gt f 01 f v2 Es V C Vg Vur Vi v2 Vs 01 v2 Es gt v1 v2 Eg 2 3 This is a decision problem much like the graph isomorphism problem The existence of both the one to one mapping f and the graph S must be tested The terms subcircuit and supercircuit are used throughout this project instead of sub graph and supergraph This terminology is also used in some of the papers that were reviewed 12 15 and it has been adopted because it highlights the fact that the graphs being compared represent circuits Chapter 2 Graph Theory 7 2 3 The Complexity of the Problem Ideally the problem should be solvable in polynomial or P time This means that for a problem involving n items there are constants c z and g such that the time taken by the algorithm T is bounded by T lt c gn 2 4 It is the constant z that is of real interest here It is called the growth factor and it indicates the amount of extra time that the algorithm can be expected to take when n is increased If z is 1 then doubling n will only d
142. e recommended method for C programs is as follows 1 Add a line to the main Makefile in your program so that the Makefile in the cr directory is called as part of your build process When the cr Makefile is called a code library called libcr a is produced in the cr directory This contains all of the circuit repository code including a C interface that will allow all the features of the circuit repository to be used from C 2 Add the libcr a code library to the linker command for your program so that the circuit repository software is linked in with your code 3 Add the linker switch 1stdc so that the standard C code library is included in the link process 4 Add the cr include directory to your include path so that the interface h header file can be included by your programs The source of interface h can be seen on page 96 5 In all the modules where you wish to use circuit repository functions the file interface h should be included The functions that are provided by this header are documented in the following section B 4 A note on handles With only two exceptions the circuit repository interface functions reguire you to supply a handle of type CR Handle You should allocate CR Handle as a variable and pass it by reference CR Handle handle rc CR Create Handle handle Handles must be initialised before any other use by CR Create Handle page 83 and should be destroyed by CR Free Handle pag
143. e search This test is so simple that there is no reason not to perform it Provided that a table like Table 5 is precomputed it will operate on n circuits in O n time because the number of different types of component is fixed In this case this test has eliminated two thirds of the search space 5 3 2 Extending this idea to net vertices The idea described above might be extended by categorising each net vertex according to the devices connected to it Whenever devices are connected together the connection is made at a net vertex so each net vertex can be assigned a type based on the connections that surround it as is already done by Luellau s algorithm see Section 3 2 3 Luellau s algorithm assigns signatures to net vertices which indicate the connections that surround them and thus their types The types of net vertex that are present in a circuit could help to identify that circuit The process would be similar to that discussed above A table similar to Table 5 1 would be generated in which every possible net vertex type was assigned a column and every circuit was assigned a row Circuits would then be screened by the types of net vertex that are present in them On first glance this idea sounds like another way to cut down the number of circuits that must be searched Unfortunately it has a serious flaw introduced by the fact that some net vertices may be open An open net vertex is a point where a circuit can be extend
144. e some weights were not correctly restored during backtracking This bug was soon fixed Testing the C Interface The C interface to the circuit repository software described in Appendix B was also tested by a program called test interface c The tests try out all of the C functions making sure that they operate according to the specification in Appendix C The tests ensure that each function works during normal circumstances Some tests also check that the error codes produced by the functions are generated correctly by feeding the functions incorrect parameters and false data Memory Handling Bug Checking A software debugging tool called Valgrind 17 was used to check for a wide variety of memory handling bugs in the circuit repository software Valgrind simulates a computer at the machine code level Every byte of data that is accessed or manipulated by the program under test is annotated with a valid bit so Valgrind is able to detect when a program makes use of uninitialised data or data in an invalid memory area It is also able to detect accesses to unallocated memory space buffer overruns and memory leaks A memory leak 1 This is a Boolean comparison The value of a true or false must be equal to the result of B Rzuper which is also either true or false Chapter 7 Evaluation 53 is a potentially serious but subtle problem in which memory is not returned by the program to the operating system when it is no
145. e subcircuit relation 3 The subcircuits of Y are all tested before Y is reached unless one of them is not a subcircuit of X This is assured by the use of a priority queue The circuit with the lowest topological order is always at the front of the queue By the definition of topological order all subcircuits of Y have a lower topological order than Y So all will be considered before Y is reached by the algorithm 4 The part of graph is connected indirect links exist between any two nodes Every item is linked to the empty circuit and the universal circuit at the very least and from there to all other items So the process of starting at the empty circuit and moving through the graph allows every item to be visited provided that each item is a subcircuit of X 5 5 7 Finding supercircuits instead of subcircuits The algorithm described in the previous section can be applied in reverse In order to do this one would simply exchange supercircuit for subcircuit start from the universal circuit instead of the empty one and reverse the order of the queue so that the item with the highest topological order appears at the front The correctness proof for this is identical to the original one This allows the second type of search listed in Section 5 1 to be carried out 5 5 8 Finding isomorphic circuits instead of subcircuits The algorithm can also be used to find circuits in the database that are isomorphic to the one supplied
146. e third phase completes but unmatched vertices remain in the smaller circuit then the matches that have been made are finalised and the algorithm repeats from phase one 3 2 3 Details of the Algorithm The algorithm matches edges net vertices and device vertices by using a property of prime numbers Any positive integer can be expressed as the product of prime factors the result of multiplying one or more prime numbers together The set of prime factors for a particular number is unique For example the number 1980 is the product of the following prime factors 22336511 There is no other multiset of prime numbers that multiply together to give 1980 This property is used by Luellau s algorithm Every edge is assigned a weight which is a prime number Assignments are made according to the type of device that it is connected to and according to which pin the edge is linked to Table 3 1 lists the assignments used by Luellau which are easily extended with new weights for the JFET and MOSFET components supported by SPICE Device Type Pin Type Edge Weight Resistor 2 NPN Transistor Base 13 Collector 11 Emitter 3 PNP Transistor Base 17 Collector 5 Emitter 7 Diode Cathode 19 Anode 23 Capacitor 29 Table 3 1 Luellau s Algorithm Edge Weights Every vertex is also assigned a weight the product of all the edge weights that are directly connected to it Because any product of prime factors uniquely ide
147. e to print out the correct translation of 7404 vertices to 7400 vertices Finally some stress tests were performed using circuits that were intended to approach worst case behaviour This was done by choosing circuits that maximise the non deterministic portion of the algorithm ones where all the vertices are indistinguishable from each other Matches based on these circuits were slow but completed correctly 3 2 6 Disadvantages of Luellau s algorithm One disadvantage of Luellau s algorithm comes from its use of products of prime factors to label vertices While this technique does allow constant time comparisons of vertices in the two circuits the number of edges that can be connected to any particular vertex is limited by the storage space available for the resulting product A 32 bit unsigned integer can take any value from 0 to 2 1 Suppose we wish to store x instances of a prime number a in this integer The product of prime factors will be a The maximum possible value of x is bounded by a lt 2 1 Any larger values of a cannot be stored Even if a is the smallest prime number two the maximum number of instances of a that can be stored in the integer is 31 If a is the largest prime number in Luellau s numbering scheme Table B1 which is 29 then x must be less than seve So in the worst case only 6 devices can be connected to a single point in the circuit This limit is rarely reached in a small analogue c
148. earlier comparisons This is no proof of optimality but it appears that no search could be more optimised unless additional information was available about the circuits Intuitively it seems that this scheme is the best There are a number of areas in which the part of graph approach may be in need of some improvement and these will now be discussed 40 A Graph Matching Search Algorithm for an Electronic Circuit Repository 5 6 1 The data structures that are used within the algorithm The description of the search algorithm made reference to two sets known and examined and a priority queue to_be_checked A hash table is a good choice of data structure to represent the sets The elements of the sets are only ever accessed randomly there is never any requirement to list all elements of the set or find the union or intersection of it Hash tables are an excellent choice for this type of set because they provide constant time access to any single element However since the maximum size of the set is known before the algorithm runs an array could be used instead An array would be a more efficient store for both sets because it would be exactly the right size to hold all elements and no larger No additional code would be reguired to deal with hash table issues such as collisions The best choice of data structure for the priority gueue would be a binary heap Binary heaps are used almost universally whenever a priority gueue is used be
149. ecord list clear Match Result rc Project Source Code 260 270 280 290 300 310 320 330 libcrdb src luellau circuit cc 132 Luellau_Circuit while rc Nondeterministic_Matching Free the edge records Edge_Record_List iterator erli for erli this gt edge_record_list erli this gt edge_record_list for erli that gt edge_record_list erli that gt edge_record_list if rc FAIL delete erli delete erli debug The matchyhas failed n gt 4s is not a ysubcircuit of s In that gt circuit_name c_str begin end begin end D this gt circuit name c str return FAIL else if rc IMPOSSIBLE D erli D erli debug Limitations of Luellau s algorithm make comparison ofuthisycircuityimpossible Nn return IMPOSSIBLE E debug The match jhas succeeded Nn s yisyaysubcircuityofy s n that gt circuit_name c_str this gt circuit name c str Build Match Record that mrl match records return COMPLETE Match Result Luellau Circuit Select a starting vertex bool cant false bool ok that Get Starting Point if ok debug No suitable starting point Everything must jbe matched Mn return COMPLETE
150. ed If a circuit C contains an open net vertex and a closed net vertex then any supercircuit of C can contain extra devices connected to the open net vertex But no supercircuit of C can ever have any extra devices connected to the closed net vertex The existence of open net vertices means that net vertex types cannot be used for reducing the search space Consider Figure The circuit on the left X is a subcircuit of the circuit on the right Y two resistors are added to X to form Y However it is very difficult to identify this relationship by looking at the types of each net vertex Each net vertex in the two circuits has been assigned a label a j The label is based only on the information available at each net vertex which pins of which devices are connected to that vertex This information allows ten different types of net vertex to be identified in the two circuits and each of these types has been assigned a different label Chapter 5 Development of an Optimised Search Method 31 9b 9c li Oc Da a Te j ha TL V ee f ha Y o Da i f d e TL h e Key 2 o Open Net Vertex Circuit X Circuit Y e Closed Net Vertex Figure 5 1 A demonstration of the problem of open net vertices Y is a supercircuit of X but the types of net vertex present in each circuit are different For example one vertex in X has signature b The equivalent vertex in Y has signature j It is possible
151. el to be used in simulating the device The reason for this omission is the difficulty of comparing models The model is defined elsewhere in the SPICE file by a card similar to this one MODEL TRANSM NPN BF 50 IS 1E 13 This model definition states that TRANSM is a model of an NPN transistor There are two parameters which are passed to the circuit simulator they define the behaviour of the transistor However this is a simple example of a model definition As Figure illustrates there can be many parameters in each model 24 Spice Manual Spice Manual 25 nane units default area BJT Parameters current where base resistance falls halfway to its minimum value S R JQ i fraction of B C depletion capacitance connected to internal base node Figure 6 1 The parameters for a bipolar junction transistor in SPICE taken from the SPICE manual 30 as it appears in the Book Emulator 3 The Gummel Poon model is used to simulate the behaviour of these transistors and all of the parameters of this model can be set using SPICE commands It is very difficult to compare one model definition with another There are huge number of parameters that may need to be compared Each is optional in the model definition so the default values will have to be known in order to carry out each comparison And each will require a different type of comparison For instance the BF parameter specifies t
152. em If it is FALSE then results are sorted by match score The results of the search are written to CR Result List which is a singly linked list in descend ing match order After use CR Result List must be freed The function CR Free Result List page B6 is provided for this purpose Returns Returns CR OK on success References See apps search_db c page 193 C Interface Reference Manual 85 CR Free Handle Synopsis CR Error Code CR Free Handle CR Handle db Description Destroys a handle and any database that might have been associated with it All memory used by the handle and the database is freed if any However memory used to store the results of a search carried out by CR Find page 84 is not freed CR Free Result List page 86 must be used for this purpose Returns Returns CR OK on success References None C Interface Reference Manual CR Free Result List 86 Synopsis CR Error Code CR Free Result List CR Result List r Description Frees the given result list Returns Returns CR OK on success References None C Interface Reference Manual 3 87 CR_Get_Error String Synopsis const char CR Get Error String CR Error Code c Description This function translates an error code into a printable English string The string may be split across several lines by newline characters but no line is longer than 80 characters The string exp
153. end 870 unmark erase uli int weight uli es erase weight Project Source Code libcrdb src luellau circuit cc 140 debug Unique else debug All 880 ifdef DEBUG debug Yedges yattached to devy s 4 dev gt name c_str Print_Edge_Map es Hendif void Luellau_Circuit Print_Edge_Map Edge_Map amp es Debug 890 Edge_Map_Iter emi for emi es begin emi es end emi Edge Info x ei emi second debug s d d u ei dev gt name c str ei net gt number ei gt weight 900 debug Nn void Luellau_Circuit Manipulate_Flags Flag_Operation_Type t Device_Vertex_List_Iter dli Net_Vertex_List_Iter nli Edge_Records_Iter eri for dli master device list begin 910 dli master device list end dli Manipulate_Flags dli t for nli master net list begin nli master net list end nli Manipulate_Flags nli t 920 for eri edge records begin eri edge records end eri Manipulate_Flags eri second t y int Luellau_Circuit Get_Luellau_Weight Type t Pin p 930 switch t case RESISTOR return 2 case CAPACITOR return 29 case DIODE return p 0 19 23 case NPN switch p 0 collector 1 bas
154. endif D 10 libcrdb include match record h ifndef MATCH RECORD H define MATCH RECORD H include lt map gt finclude lt string gt include constant time list h A match record describes a single instance of a match between two circuits It is generated by a circuit matcher namespace std struct Match_Record struct Net Match List Constant Time List paircint int gt l struct Device Match List Constant Time List pair string string gt Net Match List net matches Device Match List device matches double Score y struct Match Record List Constant_Time_List lt Match_Record gt Project Source Code 10 20 30 40 60 105 libcrdb include ohlrich circuit h endif D 11 libcrdb include ohlrich circuit h ifndef OHLRICH_CIRCUIT_H define OHLRICH_CIRCUIT_H include spice_interpreter h include constant_time_list h include match_record h include lt ext hash_map gt include lt ext hash_set gt namespace std class Ohlrich_Circuit public Spice_Interpreter public public functions Ohlrich_Circuit istream amp fd Ohlrich_Circuit virtual Ohlrich Circuit int Compare_To Ohlrich_Circuit amp t Match Record List amp mrl bool assume all open true bool only find one match false private struct Vertex List Constant Time List Vertex gt struct Partition map lt int V
155. ere are n nodes in the tree Deletions and insertions of a single node also take O log n operations And iteration through all n nodes can be performed in O n time Red black trees can replace hash tables in Ohlrich s algorithm to good effect Red black trees are slightly slower than hash tables for searches insertions and deletions Hash tables can carry out these operations in constant time if they are large enough whereas red black trees require O log n time Despite this red black trees have much higher efficiency for operations involving iterating through every item Those operations are O n A second advantage of red black trees comes from the fact that they are ordered structures Ohlrich s algorithm includes a step in which vertices with labels that appear in the larger circuit but not in the smaller circuit are removed This occurs once during each iteration In the original implementation the use of hash tables forced the original programmers to do this by a search of the hash table for the larger circuit checking each vertex against the hash table for the smaller circuit However because the items in a red black tree are stored in order two red black trees can be compared in an equivalent way in only O n steps where n is the number of vertices in the larger tree The two trees can be treated as sorted lists of vertices Simply iterating through both lists will reveal any discrepancies where a vertex is in one list and not in the othe
156. ersal Convert the circuit list into an array since the size has now been finalised db size circuit list size db new Database Record db size i 0 for c circuit list begin c circuit list end c string o db i exc e s db i sub_to_super_order 0 db i super to sub order 0 db i cr Load Circuit Directly ensure it is loaded Check each circuit for connectedness if db i cr Test_Connectedness o cout lt lt UNCONNECTED in lt lt xc Get Circuit Name lt lt u lt lt o lt lt jjare unconnected Mn itt No need for this any more Free the memory circuit_list clear Build the complete graph with all links This is the slow bit for sub_number 0 sub_number lt db_size sub_number for super_number 0 super_number lt db_size super_number Make_Link sub_number super_number Remove transitive links for sub_number 0 sub_number lt db_size sub_number for super_number 0 super number lt db size super number Remove_Transitive_Links sub_number super_number Project Source Code 440 460 ATO 480 490 500 510 125 libcrdb src database cc Calculate topological order numbers Sub To Super Set Topological Order 0 0 Super To Sub Set Topologic
157. ertex gt type dev_pin 390 bool Ohlrich_Circuit Relabel_Non_Border_Vertex_Circuit Vertex v bool open_flag progress int sum Relabel Non Border Vertex open flag progress sum v 400 if open flag else progress true update weight v weight positive sum 410 Return TRUE if there has been a change return progress bool Ohlrich_Circuit Relabel Non Border Vertex Subcircuit Vertex v bool open flag progress int sum Relabel Non Border Vertex open flag progress sum v 420 if open flag Strictly speaking we should only do this if this is the small graph v gt border true progress true else progress true update weight 430 v weight positive sum Return TRUE if there has been a change return progress bool Ohlrich_Circuit Exclude_If_Matched Vertex v return v gt assigned 440 void Ohlrich Circuit Back_0ut_Relabelling Partition p Change_List change list Change_List iterator ei 3 for ci change list begin ci change list gt end ci 450 Change_Record amp change item ci Vertex vertex change_item vertex switch change_item type case Everything case Weight Find the current location of the vertex in the partition if any it may have been deleted an
158. ertex List gt typedef Vertex List iterator Vertex List Iter typedef enum AssignedAndSafe Weight Everything Change Type typedef enum SET_BORDER CLEAR BORDER COPY OPEN NO_CHANGE Border Flag Operation Struct Change Record Changes apply to a vertex and have a type Vertex x vertex Change Type type int original weight bool original open bool original assigned bool original_safe int timecode F3 struct Change List Constant_Time_List lt Change_Record gt Ohlrich Circuit x that Partition net partition Partition dev partition Partition net partition backup Partition dev partition backup typedef bool Vertex Procedure Vertex void Initial Labelling void void Back Out Relabelling Partition p Change List change list void Save Item On Change List Change List change list Vertex v Change Type t Project Source Code 70 80 90 100 110 120 libcrdb include scored circuit h 106 bool Remove Border Nodes void Remove Diff Nodes Partition amp remove from void Find Candidate Vector Partition partition Partition amp p Vertex List amp candidate vector int Verify Image Vertex keynode Vertex List amp candidate vector void Verify Image Core Partition amp subgraph partition copy void Match Vertex a Partition amp graph partition copy Change List chan
159. esent then circuit 2 cannot possibly be present either This has the potential to significantly improve the speed of a search It is likely that many of the database circuits will be eliminated from consideration at an early stage when the lower levels of the part of graph are being examined And since the part of relationship implies a smaller than relationship the circuits at the lower levels of the part of graph are guaranteed to be smaller than those at the higher levels Thus large circuits will be eliminated from consideration by the failure of smaller circuits which can be tested more quickly because of their size The effectiveness of this approach will vary according to the number of database circuits that are subcircuits of other database circuits In some circumstances this could be a problem For example if the database contained only 74 series logic gates then one could expect even the simplest circuits to contain around five transistors The part of graph would be almost flat and most of the circuits would be on the lowest level Search performance would barely be improved by the use of the approach although it would certainly not be worsened It is possible to guarantee that the use of this approach will be no worse than searching all n circuits Careful use of graph algorithms will ensure that even in the worst cases the code that finds the next subcircuit for evaluation will run in near constant time 5 5 2 Aside empty and
160. ess of the Search Through Sorting by Size When the score feature was first added lists of results were sorted by score The best matches as determined by the score appeared at the head and poorer matches appeared towards the tail of the list This was found to produce correct but unexpected results when a search for a subcircuit or supercircuit was initiated Suppose that the search tool is being used to look for all subcircuits of a NAND gate Two subcircuits exist in the database one is another NAND gate and the other is a Darlington pair Clearly the Darlington pair is smaller than the database NAND gate but it will nevertheless get a higher score than the database NAND gate if any of the device values in the NAND gate differ from those provided by the user A Darlington pair contains no resistors capacitors or inductors so its match score is always 1 However a typical NAND gate contains four resistors so its match score may be less than be 1 In this example the larger circuit can get a lower score than the smaller one And this is quite common In some of the manual test cases Section 7 1 3 a small circuit gets a perfect score of 1 simply because all of its devices have the correct values Larger circuits with one or two slightly incorrect values get less than perfect scores This behaviour is correct but may be counter intuitive to a user who will probably take the entirely reasonable view that the largest circuits should be
161. et vertex d unique edges onunet AdNn unique edges net gt number best net vertex unique edges unique edges best net vertex found true best net vertex net If we have found a suitable net vertex then it will be the 150 starting point if best_net_vertex_found debug XYZZYuLuWillyuseunetuvertexy4dNn best net vertex gt number starting_net_vertex best_net_vertex starting_device_vertex OL return true debug No bestunetuyvertexuyfound n 160 No suitable net vertex has been found so we will have to choose a suitable device vertex as the starting point Device Vertex best device vertex OL int best device vertex unique edges 1 Device Vertex List Iter dli for dli master device list begin dli master device list end dli 170 1 Device Vertex comp dli Edge Map Bg 4 f comp gt assigned continue Get_Unique_Edges comp es 180 int unique edges es size Project Source Code 131 libcrdb src luellau circuit cc debug d uniqueLedgesyonydev 4s n unique edges comp name c_str if best device vertex unique edges LESSTHAN unique edges debug Best device vertex d unique edges on devu 4sin 190 unigue_edges comp name c str best device vertex unique edges unique edges best device vertex
162. ether circuits match or not Since the algorithm is far slower than the tests these tests have increased the speed of the search This process is called pruning removing parts of the search space that hold no solutions 29 30 A Graph Matching Search Algorithm for an Electronic Circuit Repository 5 3 1 Numbers of devices One very trivial test is to check that the set of components in the larger circuit is a superset of the set of components in the smaller circuit If the smaller circuit is truly a subcircuit of the larger one then it must have a subset of the components of the larger one To perform this test as efficiently as possible one might store a table in the database containing the quantity of each device like Table 5 1 Circuit Resistors Capacitors Inductors NPN Trans A 4 0 0 0 B 3 1 0 4 C 4 1 1 0 D 1 1 0 2 E 1 0 0 2 F 2 0 0 0 Table 5 1 Example of a database table that could allow the search tool to eliminate circuits that cannot possibly match the circuit provided by the student If the student s circuit X consisted of two NPN transistors and two resistors then circuits A B and C could not be subcircuits of X they have too many resistors Circuit D would also be eliminated because it contains a capacitor and therefore cannot be a subcircuit of X Only E and F could be subcircuits of X and these would be the only circuits that would be considered by the next stage of th
163. f another However Ablasser s method for finding graph isomorphism was developed by others into a method for finding subgraph isomorphism this is described in Section 2 4 5 Ablasser s method converts the circuit layout into a multiplace 6 graph A multiplace graph is a special type of bipartite graph A bipartite graph consists of two types of vertex which are never directly connected to each other Here the two types of vertex represent electronic components such as transistors and connection points Components are only ever connected to each other via intermediate connection points Similarly connection points are only ever connected to each other via intermediate devices In Ablasser s paper electronic components are referred to as nodes and connection points are referred to as spiders Unfortunately this terminology is confusing In SPICE a connection point is called a node Additionally some graph theorists use node as a synonym for vertex Referring to some graph vertices as nodes and others as spiders is unconventional and unhelpful Therefore Ablasser s naming scheme has not be adopted by this project Instead electronic components within a graph are referred to as device vertices and connection points are referred to as net vertices This naming scheme adopted from a paper by Ohlrich 15 does not result in any confusion with the names used by SPICE It also emphasises the fact that both electronic com
164. f the database tool in finding the problem This solution to the problem puts decisions about how to handle unconnected devices in the hands of the user The user is warned if any are present but not prevented from adding circuits that contain them In this way circuits containing unconnected devices can still be added for test purposes 7 3 Evaluating the Effectiveness of the Search Tool All of the tests in the previous section indicate that the search tool works reliably and correctly However they do not indicate anything about two important areas of its operation efficiency and usefulness In order to be effective the search must be both efficient and useful 56 A Graph Matching Search Algorithm for an Electronic Circuit Repository Efficiency becomes very important when the database of circuits is very large An efficient search will obtain correct results in a minimal number of operations and effort has been put into making the search algorithm as efficient as possible In the first part of this section the effectiveness of this will be examined The usefulness of the search tool will be examined in the second part of this section The search tool must be useful to the end user it must provide meaningful results that are helpful and informative This attribute will be evaluated by reference to the types of task that a user will be able to perform using the tool 7 3 1 The Efficiency of the Search Tool How well does the search al
165. face if this is required Chapter 7 Evaluation In the previous chapter an optimised search algorithm was described In this chapter the steps taken to verify its correctness and the correctness of the implementation will be discussed followed by a discussion analysing its performance and looking at ways in which it could be improved 7 1 Functional Testing of the Search Algorithm Ohlrich s algorithm was tested separately from the search algorithm and then the two were tested together The tests that were performed on Ohlrich s algorithm are described in Section 3 3 4 The tests that were performed on both Ohlrich s algorithm and the search algorithm are described in this section In Section Ohlrich s algorithm was tested by a variety of different methods all of which were automatic It was tested by comparison to Luellau s algorithm both were expected to produce the same results using a corpus of test circuits It was also tested using a random process that generated both a circuit and its supercircuit and confirmed that Ohlrich s algorithm detected the relationship between the two correctly Finally checks were carried out to ensure that circuits are always reported as subcircuits of themselves The tests required for the search tool are quite different Both automatic and manual tests were used and these are described in this section 7 1 1 Examining the database structure produced by the algorithms It is critically important
166. g a rule based approach In Proceedings of IEEE ICCAD pages 190 192 IEEE Press 1985 D C I Systems Daylight theory Fingerprints http www daylight com dayhtml doc theory theory finger html D C I Systems Webpage http www daylight com 73 21 22 23 24 25 26 27 28 29 30 31 32 M I Systems Available chemicals directory data sheet http www mdli com products pdfs acd_ds pdf M I Systems discoverygate database http www discoverygate com M Takashima A Ikeuchi S Kojima T Tanaka T Saitou and J ichi Sakata A circuit comparison system with rule based functional isomorphism checking In Proceedings of the 25th ACM IEEE conference on Design automation pages 512 516 IEEE Computer Society Press 1988 M Takashima T Mitsuhashi T Chiba and K Yoshida Programs for verifying circuit connec tivity of mos lsi mask artwork In Proceedings of the nineteenth design automation conference pages 544 550 IEEE Press 1982 M Turner Neural networks to support molecular structure matching http www cs york ac uk arch neural research adam molecules chem match html M Turner and J Austin Graph matching by neural relaxation Neural Computing and Applications 1997 M Turner and J Austin A neural relaxation technique for chemical graph matching In Fifth International Conference on Artificial Neural Networks IEE 1997 J R Ullmann An al
167. g of every vertex is performed Thirdly the vertices are sorted into different regions of a partition according to their labels The process is the same regardless of the type of comparison taking place and is independent of any other circuit that might be involved in the comparison Thus the results of this preparation process can be stored in the database a version of the circuit data that is ready for immediate use by Ohlrich s algorithm This will eliminate the need to carry out the process for each comparison and will speed up the algorithm accordingly As a side effect of this there is no need to undo the effects of the first phase before the second phase begins At the beginning of the second phase various flags must be cleared and the labels must be reset to their initial values T his can be easily done by restoring the prepared version again 28 A Graph Matching Search Algorithm for an Electronic Circuit Repository Chapter 5 Development of an Optimised Search Method 5 1 Rationale The previous chapter noted that there are two ways to optimise a search For one the comparison method could be optimised and this was discussed in the previous chapter For another the search method could be improved and this will be discussed now In Section 2 5 it was noted that three types of search would be possible using a circuit comparison algorithm such as Ohlrich s algorithm Specifically once a student had drawn a circuit i
168. g process is run only once Ohlrich s algorithm consistently chooses a starting point that results in a candidate vector that is the same length or shorter than that chosen by Luellau s algorithm This can be shown by a simple experiment based upon the corpus of circuits that was mentioned earlier When two circuits are selected from the corpus and compared the size of the candidate vector found by Luellau s algorithm is never less than the size of the candidate vector found by Ohlrich s algorithm regardless of the circuits that are chosen To quote Ohlrich s paper the running time remains reasonable because Phase I is usually able to find the right vertex Selecting the best candidate vector is essential for efficient matching The fact that Ohlrich s algorithm does not depend on unique edges also allows it to handle circuits in which no unique edges exist such as Figure 3 5 This is a second advantage over Luellau s algorithm A third advantage of Ohlrich s algorithm comes from the fact that the labels assigned to vertices are not fixed Vertexes are relabelled during the matching process under two circumstances e When two vertices are matched together they are both assigned a unique label that never changes e Whenever an unmatched vertex V is next to one or more matched vertices it is relabelled by a procedure that takes into account the current label of V and the labels of all the neighbouring matched vertices By doing this
169. ge Key si Edge Key s2 const return si dev s2 dev amp amp si net s2 net amp amp si dev_pin s2 dev pin F3 60 struct Edge Records __gnu_cxx hash_map lt Edge_Key Edge Info Edge Hash Edge Eq typedef Edge Records iterator Edge Records Iter Struct Device List By Weight Map _ gnu_cxx hash_map lt int Device Vertex List gt struct Net List By Weight Map _ gnu_cxx hash_map lt int Net Vertex List gt struct Edge Map std map lt int Edge Info gt 70 typedef Edge Map iterator Edge Map Iter struct Weight List list lt int gt typedef Weight List iterator Weight List Iter struct Edge Record List list Edge Info gt assigned once during preparation never changed Device List By Weight Map device list by weight Net List By Weight Map net list by weight 80 bool prepared changed during matching Edge Records edge records Edge Record List edge record list Net Vertex Starting net vertex Device Vertex Starting device vertex Luellau Circuit that temporaries used for matching 90 Net Vertex List net stack Device Vertex List device stack unsigned long operations enums enum Deterministic Matching Result NO UNIQUE EDGES COMPARISON CONFLICT OK enum Flag peration Type FINALISE CLEAR ALL CLEAR UNFINALISED 100 functions bool Get Starting Point v
170. ge list bool amp equiv class check failed bool amp progress Relabelling functions bool Relabeller Partition amp p Change List change list Vertex Procedure vp bool delete unless relabelled new void Backup void void Restore void void Reset Flags Partition amp p bool Test Equivalence Classes Vertex b Border_Flag_Operation f Partition amp subgraph partition Partition amp graph partition These ones are called by pointers static static static static static static static inline int Get Ohlrich Weight Type t Pin p bool Relabel Non Border Vertex Subcircuit bool Relabel Non Border Vertex Circuit Vertex v void Relabel Non Border Vertex bool amp open flag bool amp progress int amp sum Vertex v bool Exclude_If_Matched Vertex v bool Relabel_Neighbours_0f_Safe_Nodes Vertex v int Get A Prime int n bool Compare Net Regions return k1 first k2 inline bool Compare_Dev_Regions first J return ki first lt k2 first void Print Partition const char 1 Partition amp p bool only_find_one_match int counter match_weight y y Hendif D 12 ifndef SCORED CIRCUIT H define SCORED CIRCUIT H include ohlrich_circuit h namespace std libcrdb include scored circuit h Project Source Code Partition amp refe
171. gorithm for subgraph isomorphism J ACM 23 1 31 42 1976 S H Unger Git a heuristic program for testing pairs of directed line graphs for isomorphism Commun ACM 7 1 26 34 1964 A Vladimirescu SPICE 2G 5 User s Guide Univ of California Berkeley Dept of Elec Eng and Computer Sciences 1981 E W Weisstein Partial order http mathworld wolfram com PartialOrder html T Williams and C Kelley Gnuplot an interactive plotting program http www gnuplot info docs gnuplot html 74 A Graph Matching Search Algorithm for an Electronic Circuit Repository Appendix B C Interface Documentation This section is a user manual for the circuit repository software The manual explains the processes required to use the circuit repository software from any program You may also find the reference manual in Appendix C useful The circuit repository software archive is called cr tar gz It is available from the online project library at this address http www cs york ac uk library In addition the source code in the archive can be found in Appendix D of this report B 1 Prerequisites The circuit repository software has been built and tested on Slackware Linux systems both inside and outside of the Department It should build on any Unix system provided that the following packages have been installed e GNU Make version 3 80 or later e GNU C C compiler version 3 2 3 or later e GNU ISO C library
172. gorithm reduce the search space Some of the tests described in Section take a circuit X from a test corpus and search for supercircuits and subcircuits of that circuit This is done for every circuit that is available and checks are performed on the lists of supercircuits and subcircuits that are produced to ensure that they contain the correct results These tests make an ideal basis for an experiment to see how well the search algorithm is able to eliminate circuits from consideration which is in effect the measure of its efficiency The database and test corpus consist of 27 circuits and one would expect that some circuits would be eliminated from consideration during each search The number of comparisons that actually take place during each search was determined by modifying the test software so that it printed out the number of executions of Ohlrich s algorithm that were required This data was organised into a histogram Figure which shows that most of the searches required far fewer than 27 comparisons 54 searches were performed in total 27 subcircuit searches and 27 supercircuit searches and only three of those searches required 27 comparisons Most required less than 15 5 FA Subcircuit Searches J Supercircuit Searches 44 CIRIE ZII UM v
173. gree degree iter2 second 560 if known count circuit 0 known circuit gt degree ok false break break case SEARCH_FOR_EQUIVALENT 570 assert 0 should have been changed to break SEARCH_FOR_SUBCIRCUIT earlier if ok continue c is not of interest Ok now we are ready to evaluate it properly switch st case SEARCH_FOR_SUBCIRCUIT degree for this Is Subcircuit c mrl true 580 Sf only find first match Sf sort by match size break case SEARCH FOR SUPERCIRCUIT degree c Is Subcircuit for this mrl true Sf only find first match Sf sort by match size break case SEARCH FOR EQUIVALENT assert 0 should have been changed to 590 break SEARCH FOR SUBCIRCUIT earlier if degree 0 continue c is not of interest Project Source Code 127 libcrdb src database cc Now we know for_this is a supercircuit of c or c is a supercircuit of for_this depending on which type of search we are running known current degree 600 switch st case SEARCH_FOR_SUBCIRCUIT Merge to_be_checked queue_type db current supers break case SEARCH_FOR_SUPERCIRCUIT Merge to_be_checked gueue_type db current subs break case SEARCH_FOR_EQUIVALENT assert 0 should have been changed to 610 break SEARCH_FOR_SUBCIRCUIT earl
174. h in Figure In this figure six circuits have been drawn The arrows indicate a part of relationship X Y indicates that X is a subcircuit of A graph like Figure can be pre computed and stored in the database This operation is unlikely to be trivial but it is only done once and it brings significant benefits Specifically the search will not need to examine all n circuits It must examine all of the ones at the lowest level of The subcircuit relation actually ceases to be transitive if vertices may be closed This problem is addressed in Section Chapter 5 Development of an Optimised Search Method 33 2 M v4 3 nan 1 Sa d 4 as inn n highest level lowest level Figure 5 3 Example of a part of graph in which X Y indicates that X is a subcircuit of Y Circuit 4 is a subcircuit of circuit 5 and so on Note transitive edges have been removed by a process that will be explained later and the reflexive nature of the subcircuit relation is ignored for the purposes of generating a part of graph the graph 6 3 and 4 in Figurel5 3 but at higher levels there is no need to examine any particular circuit X unless all of the circuits that are known to be subcircuits of X are present For example there is no need to examine circuit 2 unless both 6 and 3 are present Circuits 6 and 3 are subcircuits of 2 so if one of them is not pr
175. h s algorithm is therefore potentially faster 2 5 The best direction to take The research that has been examined has involved several different graph isomorphism algorithms which all make use of the special properties of circuits Circuits are special types of graph They can be labelled in ways that make the matching process easier as has been done by Ablasser Luellau and Ohlrich Thus circuit matching is not necessarily as difficult as the general subgraph isomorphism problem although as will be proved in Section 3 2 4 this case of the subgraph isomorphism problem is still NP complete The papers that have been reviewed have made it clear that circuit matching is possible and efficient algorithms to do it already exist It would certainly be possible to implement for example Luellau s algorithm and use it as the core of the search tool It is possible to do three things all of which may be of use to a student learning about circuits e The student may draw a complete circuit and then use the search tool to make a list of circuit fragments in the database that are part of it i e its subcircuits Since the database will include descriptions of those circuits this will help to explain the operation of the student s circuit e The student may draw a fragment of a circuit and ask in which of the database circuits it can be found e Any circuit in the database that is isomorphic to the student s circuit can be found since any subg
176. h the vertices of the subcircuit to those of the circuit The borders between the vertices that are labelled in one iteration and those that are labelled in the next are indicated by dotted lines T he set of matched vertices grows until all subcircuit vertices have been matched 8 7 Ed o4 8 7 m 7 6 6 Ri R2 R4 E PB RE m R4 5 4k 1k6 130 So LA 1k6 130 S ier NUNC IN ens e r r Xii ae 23 3 el 3 p Po 0 2 lo oF ig 2 iisyb rv 6 93M 1 03 GM AAS se 2 P E98 2 En lt Me SS 30 3 R3 Ik 4 ME o 0 unmatched 8 ET 165 5 i 8 7 36 5 Figure 3 4 An example of Luellau s algorithm in action with the vertices that are matched at each iteration separated by dotted lines The circuit on the right an inverter is a subcircuit of the circuit on the left a NAND gate In the first iteration marked 1 Dk is matched to D3 Then during the next seven iterations net vertices and device vertices are matched up The third phase may fail in which case the algorithm will return to the second phase and make 18 A Graph Matching Search Algorithm for an Electronic Circuit Repository a different choice If no choices remain then the circuits do not match and the matching function will return FALSE Sometimes the algorithm will take more than one iteration to match everything If th
177. he bridge rectifier circuit on the left can be represented as a graph right The diodes have been represented by graph edges and the connection points have been represented by vertices Representing a circuit as a graph makes it possible to apply graph algorithms to it algorithms that solve problems that are expressed as graphs In particular graph comparison algorithms can be applied The circuit comparison problem is a decision problem is a smaller circuit a part of a larger one To be a part of the larger circuit the smaller circuit must have a subset of the larger circuit s components and all of the components in the smaller circuit must have the same connections as those in the larger circuit If both circuits are expressed as graphs then testing whether the smaller graph is a part of the larger one is an equivalent problem This problem is called the subgraph isomorphism problem and it has been looked at in detail by graph theorists over the last forty years The subgraph isomor phism problem is more general than the circuit comparison problem which gives some opportunity for improving the methods used to solve it Subgraph isomorphism algorithms do not provide any way to compare the values of the devices within a circuit such as the resistance of a resistor However since they can match the devices in one circuit to those in another a direct comparison can be made once isomorphism has been detected The application of subgra
178. he ideal gain 8 of the transistor Transistors are normally operated in such a way that the exact value of the gain is not important so 8 200 is essentially the same as 6 150 The degree of importance that should be attached to each parameter would have to be worked out Comparing SPICE models is a substantial problem in itself and it is one which must take the circuits in which the models are used into account because particular parameter settings may have more effect in some circuits that others It is beyond the scope of this project to attempt to compare SPICE models It should be noted that the model information is already used by SPICE Interpreter to deter mine the type of each transistor NPN or PNP This is all that is needed for the most part users are unlikely to be concerned with model settings and may even be puzzled if two identical circuits do not match because the model settings in one are incorrect Just comparing the values of resistors capacitors and inductors is sufficient to compare the values present in a circuit This is much easier since each device has only one parameter a positive non zero real number Chapter 6 Adding a Device Value Comparison Feature AT 6 1 2 Assigning a score If matches are to be ranked the comparison procedure will need a way to produce a score for a match of two circuits X Y There are plenty of ways to score the match between two circuits but a scoring system will have to ha
179. he performance of one of the heuristics The resulting heuristic would have to either fully solve the subgraph isomorphism problem in which case it would certainly be no better than Ohlrich s algorithm or just examine more of the structure in order to eliminate circuits that could not match In this case it would still be possible to construct a circuit that could fool the heuristic into thinking that a match could exist Whatever direction was taken improving the heuristics would be a lot of work for no gain 5 5 Improving the search method In the previous section a few ways to cut down the search space were discussed They can improve the speed of a single circuit comparison and thus the overall speed of a search but they do not do anything to optimise the search method Ideally a search program should minimise the number of circuit comparisons it carries out by eliminating as many circuits from consideration as possible while maintaining the accuracy of the results 5 5 1 A part of graph After some thought a method to optimise the usage of a circuit comparison algorithm was invented The method uses Ohlrich s algorithm and applies it in a way that makes the best use of it It was observed that the relation of subcircuit is transitive That is if A is a subcircuit of B and B is a subcircuit of C then A is a subcircuit of C This makes it possible to sort the circuits into a partial ordering 31 as has been done in the grap
180. ial and the algorithm will take an exponential amount of time to complete Even for quite small numbers of variables it will probably take so long that it is not worth attempting Ullmann s algorithm is not a computationally tractable method for detecting subgraph isomor phism in sufficiently large graphs because the worst case time complexity is O e if the larger graph has n vertices Fortunately this is only true for a general instance of the subgraph isomorphism problem In specific instances the time taken for a subgraph isomorphism algorithm to complete is much less than O e For example Eppstein 7 has described an algorithm for some graphs that can solve the problem in linear O n time His algorithm uses a divide and conquer approach and any guessing that is done is guaranteed not to take an exponential length of time However Eppstein s approach is only useful for planar graphs ones which can be drawn in such a way that edges do not cross each other An electronic circuit of any complexity is unlikely to be planar But there are other properties of circuits which can be used to speed up a subgraph isomorphism algorithm In the representation of a circuit seen in Figure edges are labelled with the component they represent and they are directed Both of these properties will reduce the number of possible mappings from one circuit to another clearly a vertex that is adjacent to two resistors cannot possibly map to one that is adja
181. ices are slow During most com parisons there is only one possible way to match the circuits involved and Ohlrich s algorithm runs quickly After choosing a key vertex and candidate vector the algorithm never returns to the non deterministic phase of operation But in certain circuits some devices are indistinguishable and there are several ways in which the circuit can be matched to another In these cases the algorithm must make a choice between them The worst case in which this occurs is when a circuit containing unconnected devices is matched to another An unconnected device has absolutely no connection to any other device it is an isolated device in the circuit Generally there are many ways to match the unconnected devices to each other If there are n unconnected devices of the same type in both circuits there will be n ways to match them to each other If Ohlrich s algorithm is attempting to find all possible ways to match the two circuits there will be at least n matches each with a different selection of unconnected devices Therefore the number of matches will grow exponentially with the number of unconnected devices Fortunately there is no practical reason for a circuit to have unconnected devices No current will flow in an unconnected device they serve no purpose whatsoever It is known that unconnected devices may occur in circuits by mistake as the example of the NOR gate demonstrates It can be assumed that when unc
182. icular sort of device This information simplifies the subgraph isomorphism problem and reduces the amount of time it takes to run It is always possible to construct a circuit that provides no additional information such as the one described in part 3 of the above proof which had only one type of component But a typical circuit will contain a wide range of different components interconnected in distinctive ways and this will be far easier to match 3 2 5 Testing the implementation A simple way to test the implementation of the algorithm is to use the example circuits described in the paper The paper uses these circuits to explain what the algorithm should do at each stage and describe what it should output A debugging build of the Luellau Circuit class was used which printed out information about every decision made The circuits under test were taken from 20 A Graph Matching Search Algorithm for an Electronic Circuit Repository the paper The output matched the description given in the paper and the match that was found was identical This provided a good indication that the implementation was correct Later tests were performed on a small corpus of circuits from a course in digital circuit design featured in the Book Emulator 3 These circuits were primarily ones from the 74 series of integrated circuits For example a 7404 inverter is a subcircuit of a 7400 NAND gate and Luellau s algorithm was able to detect this It was also abl
183. idate vector and a key node assert that gt net partition assert that gt dev partition empty Remove Diff Nodes this gt net partition return 0 f this gt net_partition A net vertex will be the key node Find the smallest of all remaining partitions Find_Candidate_Vector this gt net_partition candidate_vector assert that gt net_partition count candidate_vector empty J M S Chu empty keynode Vertex that net partition candidate vector assert keynode OL begin gt weight debug XYZZYuOunetukeynodeunumber_4dVn Net Vertex keynode gt number ready for phase 2 Vertex List Iter vli for vli candidate vector begin vli candidate vector end vli Vertex x candidate x vli Vertex_List short_vector this gt Restore that gt Restore this gt Initial_Labelling that gt Initial_Labelling Reset_Flags Reset_Flags Reset_Flags Reset_Flags short_vector if mc gt 0 this this that that gt net partition gt dev partition gt net partition gt dev partition push_front candidate int mc Verify_Image keynode shor Project Source Code NO_CHANGE NO_CHANGE NO_CHANGE NO_CHANGE 5 t vector Ja begin
184. ier if c Is_Special If this circuit is empty universal do not add it to the results continue 620 if find_equivalents If we are searching only for circuits that are equivalent to for_this then an extra refining step is needed Specifically c must be a supercircuit of for_this Match_Record_List mrl2 if c Is Subcircuit for this mrl2 false true Sf sort by match size 0 630 continue assert mrl empty Search Result Record Bf double key sr match record list mrl 640 Sr circuit c if sf sort by match size sort by match size key mrl front net_matches size mrl front device matches size else sort by score key mrl front score 650 H results map insert pair lt double Search Result Record key sr if sf dont_assume_open amp amp st SEARCH_FOR_SUPERCIRCUIT amp amp for this Contains Closed Net Vertices Refine the results Examine everything that has been put into the results map removing circuits if 660 the circuit contains closed net vertices and a rematch of for_this and the circuit taking the closed net vertices into account fails Brrrrk A ek o to rematch_count 0 degree 0 Project Source Code 670 680 690 700 710 10 20 libcr
185. if Type_To_String INDUCTOR compare s 0 return INDUCTOR else if Type_To_String NPN compare s 0 return NPN else if Type_To_String PNP compare s 0 return PNP else if Type To String NMOS compare s 0 return NMOS else if Type To String PMOS compare s 0 return PMOS else if Type To String NJFET compare s 0 return NJFET else if Type To String PJFET compare S 0 return PJFET return UNKNOWN void Spice Interpreter Net Vertex Connection List v gt connected for i Device Vertex x if Test_Net_Connectedness iterator r true V gt connections 5 i begin v2 v2 connected i device Test Device Connectedness v2 void Spice_Interpreter Net_Vertex v v gt connections Test_Device_Connectedness Device_Vertex_Connection_Map iterator v gt connected true for i v gt connections begin i Net Vertex v2 i second if Test_Net_Connectedness string Spice_Interpreter char buffer snprintf buffer D v2 connected v2 v gt connections Int To String int i 32 31 3 yd dues return string buffer bool Spice_Interpreter Device_Vertex_List_Iter Net_Vertex_List_Iter Test_Connectedness dli nli clear connected flag f
186. ight be supplied to it One way to ensure that the graph has this property is to add some new dummy circuits to the database so that every circuit has several subcircuits Careful choice of these new circuits could allow the search tool to eliminate many of the real circuits early in the search process However it is not clear at present how the circuits would be generated so this will be addressed again in a later chapter 5 6 3 Labelled graph edges A possible way to improve the approach would involve labelling each graph edge with the number of subcircuits that would need to be present Suppose that circuit A is a four input AND gate and it consists of three two input AND gates As circuit B is a two input AND gate B is a part of A However at least three copies of B must exist in a circuit X if A could be a subcircuit of X The edge between A and B could be labelled with 3 to indicate this The degree of that edge is 3 It is possible to modify the circuit matching algorithms to indicate the number of instances of a subcircuit that were found in a larger circuit In the case above if at least three copies of B were not found in X there would be no point in considering A The modifications required are not complicated The test that checks that all subcircuits of the current circuit are present must be modified to check that they are present in the correct numbers A new data structure is also added to store the number of o
187. igned type assert type gt 0 amp amp type lt number of types counter type bool Serialisable_Signature Is_Subset const Serialisable_Signature amp sub const if number_of_types sub number_of_types for unsigned i 0 i lt number of types i return false if counter i lt sub counter i return false return true bool Serialisable_Signature Write ofstream amp out const bool rc Write_Magic out Project Source Code 100 110 120 130 10 20 167 libcrdb src spice_interpreter cc amp amp Write Integer out number of types for unsigned i 0 i lt number of types i return rc rc rc amp amp Write Integer out counter i bool Serialisable Signature Read ifstream amp in if number_of_types gt 0 delete counter bool rc Read_Magic in amp amp Read_Integer in number_of_types assert number of types gt 0 if number of types gt 0 counter new unsigned number of types for unsigned i 0 i lt number of types i return rc rc rc amp amp Read Integer in counter i D 31 libcrdb src serialisable string cc include serialisable_string h using namespace std bool Serialisable_String Write ofstream amp out const The string is written to
188. igure the empty circuit has a topological order of 0 5 5 4 Generating a part of graph A simple algorithm to generate a part of graph is described here No attempt to ensure that the algorithm is optimal has been made since this algorithm is used only during database builds The graph consists of three pieces of information for every circuit X e A set of supercircuits of that circuit supersx e A set of subcircuits of that circuit subs y e The topological order of that circuit The algorithm that derives this information begins with a set of all circuits which will be called S It operates on that set as follows 1 For every circuit A in S let supers contain only the universal circuit 2 For every circuit A in S let subs contain only the empty circuit 3 For every circuit A in S Chapter 5 Development of an Optimised Search Method 35 6 2 vd E Tei 3 Ta B a Pe E B X M empty circuit y universal circuit 4 lt zx bs 5 M ou 1 Bl MEN 4 seen Sg ue j Al a 1 highest level lowest level Figure 5 4 Example of a part of graph including topological order numbers in square brackets a For every circuit B in S i If A B return to step Ba Each circuit is a subcircuit of itself but this fact is not useful during the generation of the part of graph ii Run Ohlrich s algorithm to test if A is a subcir
189. igures produced in Xfig 3 2 Statistical graphs were produced using Gnuplot 32 and directed graphs were produced using daVinci 9 2 1 Histograms and bar charts were produced using OpenOffice 1 1 T he figure on page 46 was taken from a screen shot of the Book Emulator 3 71 72 A Graph Matching Search Algorithm for an Electronic Circuit Repository A 2 References 1 I Ablasser and U J ger Circuit recognition and verification based on layout information 10 11 12 13 14 15 16 17 18 19 20 In Proceedings of the eighteenth design automation conference on Design automation pages 684 689 IEEE Press 1981 K Barnaby Towards a circuit repository schematic to spice converter 3rd Year Computer Science Project University of York 2004 I D Benest A schematic entry drawing capability in a linearised hypermedia system J CGF 13 5 293 303 Dec 1994 D G Corneil and C C Gotlieb An efficient algorithm for graph isomorphism J ACM 17 1 51 64 1970 C Ebeling The gemini netlist comparison project http www cs washington edu research projects lis www gemini gemini html W L Engl and D A Mlynski Theory of multiplace graphs IEEE Transactions on circuits and systems 22 1 2 8 1975 D Eppstein Subgraph isomorphism in planar graphs and related problems J Graph Algo rithms Applications 3 3 1 27 1999 C L Forgy OPS5 User s Manual Carnegie
190. ill also print out a warning if any component in any circuit is found to be disconnected from the rest of the circuit 78 A Graph Matching Search Algorithm for an Electronic Circuit Repository Appendix C C Interface Reference Manual The following chapter contains a reference manual for the C interface to the circuit repository software 79 CR Add Circuit 80 Synopsis CR_Error_Code CR Add Circuit CR Handle db const char c file Description Add a circuit to the database A path to the circuit s file which should be in SPICE format must be provided Paths can be relative or absolute but it is better to use absolute paths because the path that is specified will be stored in the database and provided as part of the search results The circuit file must remain available until the database has been built but after that it may be moved or deleted as its contents are copied into the database Please note that circuits cannot be added to any database after it has been built They can only be added after a call to CR Create Database page 82 and before a call to CR Build page 81 Returns Returns CR_OK on success References See apps build_db c page 91 C Interface Reference Manual 81 CR Build Synopsis CR Error Code CR Build CR Handle db Description Builds the database A part of graph is generated for the entire database using the algorithm described in Section 5 5 1 This can
191. ing search system but this would fail to make best use of its capabilities To really make use of RBE the project would need to be repeated with the intention of applying relaxation labelling techniques in mind from the very beginning RBE is certainly a topic for future work It promises significant benefits which will be well worth researching if the circuit repository that has been developed here proves to be inefficient in practice or a need for partial matching is found However it is the author s belief that the circuit repository software will work well in practice No assumptions have been made about the number of circuits that will be stored nor the structures of those circuits All the algorithms used in the software are very general and capable of handling any circuits The search algorithm is as efficient as possible given that its only source of information about the circuits is Ohlrich s circuit matching algorithm These features will allow the software to scale so that large databases can be managed without difficulty Appendix A Acknowledgements and References A 1 Acknowledgements The author would like to acknowledge the following contributions to this work e Dr Ian Benest the supervisor of this project who kindly reviewed various drafts of the report and made many suggestions about its development Dr Benest also drew some of the circuits used for testing the software e Keffin Barnaby who provided more of the cir
192. ing the Effectiveness of the Search Tool LL 55 7 3 1 The Efficiency of the Search Tool PP a 56 7 3 2 The Usefulness of the Search Tool a 60 V kr Se a Eh te 61 8 Conclusions and Future Work 65 ITI 65 aja ORE mai NIETO T 66 A E a ea a 67 MT 67 SETS 69 vi TABLE OF CONTENTS TABLE OF CONTENTS 8 4 Conclusion aaa 70 A Acknowledgements and References 71 A 1 Acknowledgementsi lll ss 71 A 2 References 72 B C Interface Documentation 75 B l Prerequisites LL 75 S 75 SEE 76 n 76 VENE e 76 A O MERO 77 gave zeds ease 77 79 CROCI WW 80 TRA 81 PROSA POETA 82 A ome bee ede ee bee 83 CREMA spia aa t s a wR i aja E E nuo ee A A 84 A A AO 85 AA Still 86 as A ES 87 ss saint 88 sg asu sa OR ORE qu Ba 89 91 O hae T ada 91 Medal A ld al 92 no dd S S 93 Low 400m Work a dedo Bed ene 96 OO ES 97 eat RM IE ZE ene 98 vc MERCIER 100 X ATTE 100 ne det ia wy b ROW RNC aie EY AE 102 Ba ccc VE M 104 eG ae xo ge I det ed dm aed ie ka 105 IB E Ga RE Ne RN i 106 be eee ee ae ee COREA ATO 107 Pi et ga da augs 108 ada dd 109 AA ds ad e 8 110 An 1 SS pais pd 112 sams ee S 113 algas TTE 114 IEM a ae 114 vr PIN A 118 as S GA oda 119 S S shee 119 ed Laine 128 Vag beste al beens oe 142 sa a V ao 158 vil TABLE OF CONTENTS TABLE OF CONTENTS su C 160 LARA RRA ee 162 ax p a a 165 sama Ta re og odes ids 167 asa 167 ere gam SM A 181 viii List of Figures
193. ingimatch of s tou 4s Nn dvp gt name c_str dv gt name c str Edge Map dvpl Edge Map dvl Are any net vertices connected to dvp already assigned If so we must verify that the assignment is the same in dv Find unique leg pairs incident to dvp that gt Get Unique Edges dvp dvpl Find unique leg pairs incident to dv this gt Get Unique Edges dv dvl For all unique leg pairs compare the net vertices connected to them You should be able to match them all up Store each Spider in the spider stack if successful If not then comparison conflict Redo from start if dvl size dvpl size XX ox o X Project Source Code 135 libcrdb src luellau circuit cc debug Comparison conflict on number of_edgesu duvsu d Nn dvpl size dvl size comparison conflict true break Edge Map Iter emi for emi dvpl begin 500 emi dvpl end emi int weight emi first Edge Info x eip emi second if dvl count weight 0 debug Comparison conflict edge of weight Ad notypresent n weight comparison conflict true 510 break Edge Info x ei dvl weight Net Vertex x nv ei gt net Net Vertex nvp eip gt net if ei assigned debug uuComparisonyconflict jedgejassigned Sn
194. iniem gt E E ies A N c 0 D 4 N ERA A al a e di s cmi cus it Z A 1 PA di aA PA ITB A VA uiu Ni A T gt DAR iki a 0 T T T T T T T T T T T T T Y T T T T T T T T T T T T T 1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 Number of Applications of Ohlrich s Algorithm Required Figure 7 3 A histogram showing the number of applications of Ohlrich s algorithm that were required during a sample of 54 searches The mean number of comparisons required by a subcircuit search is 8 7 slightly less than the 11 5 comparisons that are required by the average supercircuit search This data indicates that the search algorithm is effective in reducing the number of circuits that need to be examined it cuts the search space to about a third of its original size on average It is a demonstration of the search algorithm s ability to improve the efficiency of a search Chapter 7 Evaluation 57 How quickly does the search algorithm operate The data does not show how fast the search can run In order to give some indication of the speed of the search process a program was written to time the execution of the Search procedure The program uses some of the test circuits used to generate the data for Figure 7 3 For each test circuit X and each type of search the program runs the
195. ircuit Most devices are only connected to a few other devices But exceptions occur all the time in large circuits consider how many devices are connected directly to ground The problem cannot be offset simply by using larger integers Using 64 bit integers will still bring a worst case limit of just 13 devices It is possible to use variable precision integers which can store any number that will fit in the memory space of the computer But operations on these numbers are not constant time and so the advantage of using prime factors has been lost However the problem can often be ignored Luellau certainly makes no mention of it in the paper This is probably because the labels generated by the prime factor method still identify vertices almost uniquely even if a multiplication overflow occurs during calculations Only one property is lost due to overflow If net vertex y is equivalent to open net vertex z with some extra components then y is divisible by x But if an overflow occurred during the calculation of y then this does not hold not least because y is now less than x Because this property is not always required to hold the algorithm may perform as expected even if an overflow occurs Then again it may not subtle bug has been introduced A second disadvantage of Luellau s algorithm was found only after extensive testing It is a flaw in the algorithm that occurs only in rare cases but is a potentially serious problem Luellau
196. ircuits of Y cannot be subcircuits of X For example in Figure 5 3 circuit 5 has two subcircuits 3 and 4 The subcircuits 3 and 4 are checked against X before 5 is checked against X If either is not present in X then 5 cannot be present in X either 5 5 6 Proof of correctness how is it possible to be certain that all subcircuits are found One question arises from the use of the algorithm how is it possible to be certain that all the subcircuits of circuit X in the database will be found In this section a proof of the algorithm s correctness will be outlined The proof assumes that both Ohlrich s algorithm and its implementa tion are correct 38 A Graph Matching Search Algorithm for an Electronic Circuit Repository The proof must show that every subcircuit of X that is in the database is considered by Ohlrich s algorithm The algorithm tries to minimise the number of circuits that are tested by Ohlrich s algorithm that is how the search is optimised It must be shown that no circuit is incorrectly eliminated from consideration 1 A circuit Y is only considered as a possible subcircuit of X if every subcircuit of Y in the database has a been considered as a possible subcircuit of X b been tested by Ohlrich s algorithm and found to be a subcircuit of X 2 If a subcircuit of Y was considered and found not to be a subcircuit of X then it would be known that Y is not a subcircuit of X due to the transitive nature of th
197. is repository several tools are required Firstly circuits must be drawn for inclusion in the repository It is possible to specify them manually using a common format such as SPICE 30 but this takes a long time To this end a tool is being developed that can take an existing drawing of a circuit from an electronic book known as the Book Emulator 3 and convert it into SPICE format for inclusion in the repository This tool makes it easy to draw new circuits using the drawing tools in the Book Emulator and the large number of circuits that have already been drawn can be included in the repository without any need for tedious manual conversion Secondly all of the circuits that are available must be built into a repository in such a way that they can be searched easily Each circuit will be annotated with a link to a description in an electronic book and any other relevant documentation that the designer of the circuit sees fit to include The repository must be kept free of duplicates so any tool that adds a new circuit to it must check that the new circuit is different to any existing ones Thirdly a search tool is required that can compare a new circuit to those in the repository It is envisaged that users will be able to draw a circuit and have it matched against the repository in order to find circuits that contain it that are similar to it or circuits that it is a part of This will bring users to documentation about related circuits how
198. it Circuit Manager amp sub Match Record List amp mrl bool assume all vertices are open bool only find one match bool sort by size EBUG lt lt nIs_Subcircuit ycalled n lt lt Qusupery y lt lt Get_Circuit_Name lt lt Nn lt lt uusubu u lt lt sub Get_Circuit_Name lt lt Nn deg circuit gt Compare To sub circuit mrl assume_all_vertices_are_open only_find_one_match sort_by_size EBUG lt lt uvdegreeu u lt lt deg lt lt Nn return deg Project Source Code 10 20 30 40 119 libcrdb src database cc D 23 libcrdb src cr exceptions cc include cr exceptions nh using namespace std const char x Std database not built database not built const char x std database already built databasejalreadyubuilt const char x Std file access error file accessyerror const char x Std file format error file formatyerror D 24 libcrdb src database cc include lt assert h gt include set include cr_exceptions h include database h static const unsigned MAGIC_NUMBER_2 0x7e07icia using namespace std Database Database Serialisable Serialisable Circuit Record empty Serialisable Circuit Record SPECIAL EMPTY ready false circuit list clear Add Circuit empty Database Database if ready delete db internal function
199. it that would make the search algorithm behave poorly None of the circuits in the graph are subcir cuits of each other so there is no optimal order in which to examine the circuits They must all be examined using Ohlrich s algorithm no information is gained about any other circuit when one of them matches or fails to match The part of graph could be improved by the insertion of dummy circuits Figure 8 2 shows the result of adding two new dummy circuits X and Y When the algorithm is searching for subcircuits of a user provided circuit the two dummy circuits will be evaluated before the real circuits If X is not present then Hex inverters and 2 input NAND gate are both eliminated from consideration And if Y is not present then 2 input NAND gate and 2 input NOR gate are both eliminated This allows the search algorithm to explore the search space in a more optimised way it does not have to examine all three of the real circuits unless there is evidence from the examination of X and Y that doing so will be worthwhile 65 66 A Graph Matching Search Algorithm for an Electronic Circuit Repository _empty circuit_ 0 2 input NOR gate p14 c1 1 2 input NAND Hex inverters f p34 c1 p30 c1 1 universal circuit 2 Figure 8 1 A pathological example of a part of graph None of the circuits in the graph are subcircuits or supercircuits of each other with the exception of the e
200. it of B and B is a subcircuit of C but A is not a subcircuit of C This cannot be allowed to occur in the part of graph The algorithms described earlier rely on the transitive property of the subcircuit relation so transitivity must be preserved There are two possible ways to do this Firstly the implementation of Ohlrich s algorithm could be modified to require that any closed vertex in the subcircuit can only ever be matched to a closed vertex in the supercircuit This would preserve the transitive property in the example above because B would not be a supercircuit of A However it would have an unpleasant side effect If users searched for the subcircuits of a circuit they had drawn the results would be limited to those circuits where the open closed properties of the vertices matched those in the user s drawing This is not desirable why should users of the search tool be forced to mark vertices as open or closed in their drawings simply in order to obtain any results A second way to preserve the transitive property is to assume that all vertices are open while generating the part of graph and running the search algorithm This method is far more practical it puts no additional requirements on the user of the search tool Once a list of results has been obtained in this way the circuits in the results that contain closed vertices can be checked again to make
201. ithm outlined in steps 1 through 3 generates a com plete graph in which edges exist for every relationship between two circuits n example of this is illustrated in Figure a The algorithm that has been devised for the search tool makes use of the transitive property of the subcircuit relation namely that if A is a subcircuit of B and B is a subcircuit of C then A is a subcircuit of C 36 A Graph Matching Search Algorithm for an Electronic Circuit Repository Circuit a Circuit b universal 1 circuit lt ys ___ ul Figure 5 5 Transitive edges are removed from part of graph a to leave the edges present in b The process of removing transitive edges ensures that the length of the path between two circuits in the part of graph is maximised This maximises the information that is available to the algorithm to allow it to eliminate circuits Whenever a long path between two nodes exists like A B C it will be kept in preference to a shorter path such as A C When the process is applied to a part of graph the result is something like Figure s A simple algorithm to remove transitive edges is as follows 1 For every circuit A in S a For every circuit B in S i If A Z subsp return to step Lal because no edge exists to directly link A and B ii Search the part of graph for
202. l Serialisable Read Integer ifstream amp in unsigned amp x const ifdef BINARY MODE uint32 t xd v in read char amp xi sizeof xi x ntohl uint32 t xi return true else string str getline in str if str length gt 0 const char start ptr str c str char check ptr x unsigned strtol start ptr amp check ptr 10 return check ptr start ptr return false endif bool Serialisable Write_Magic ofstream amp out const bool Serialisable Read_Magic ifstream amp in const return Write_Integer out MAGIC_NUMBER_1 unsigned mn bool rc Read_Integer in mn assert rc amp amp mn MAGIC_NUMBER_1 return rc amp amp mn MAGIC_NUMBER_1 bool Serialisable Write_Unsigned_Map ofstream amp out Unsigned_Map amp map const bool rc 4 Unsigned Map iterator i 4 rc Write Integer out map size for i map begin i map end i rc rc amp amp Write Integer out i first amp amp Write_Integer out i second return rc bool Serialisable Read Unsigned Map ifstream amp in Unsigned Map amp map const bool rc Project Source Code libcrdb src serialisable circuit record cc 162 unsigned SZ yd cXo wy rc Read Integer in sz for i
203. l n 970 We failed Must try the next item in the candidate vector We d better back out the changes that we made Note doesn t matter what partition we give to this Back_0ut_Relabelling NULL amp change_list No more items 980 return mc bool Ohlrich_Circuit Relabel_Neighbours_0f_Safe_Nodes Vertex v bool relabel false Device Vertex Connection Map Iter cmi Net Vertex Connection List Iter cli int sum 0 990 if v assigned If this vertex is not assigned and it borders a safe assigned node then it needs to be relabelled also it must not be in the current candidate vector as passed to the calling Project Source Code 155 libcrdb src ohlrich circuit cc Verify Image assumption 1000 if v is net Net Vertex vertex Net Vertex v for cli vertex gt connections begin cli vertex gt connections end cli Device_Vertex dev cli gt device Pin dev pin cli gt device pin 1010 if dev safe relabel true sum dev gt weight Get Ohlrich Weight dev type dev pin else Device Vertex vertex Device Vertex v 1020 for cmi vertex gt connections begin cmi vertex gt connections end cmi Net Vertex x net cmi second Pin dev pin cmi first if net safe relabel
204. lains the reason why the error has occurred Returns The pointer that is returned points to a string in a read only string table and should not be freed References None C Interface Reference Manual CR_Load_Database 88 Synopsis CR Error Code CR Load Database CR Handle db const char db file Description Loads a database from a file on disk Returns Returns CR OK on success References See apps search db c page C Interface Reference Manual 89 CR_Save_Database Synopsis CR Error Code CR Save Database CR Handle db const char db file Description Saves a database to a file on disk The database must already have been built by CR Build page 81 Returns Returns CR_OK on success References See apps build_db c page 91 C Interface Reference Manual CR_Save_Database 90 C Interface Reference Manual 10 20 30 40 Appendix D S D XA X X ource Code 1 apps build db c build db c Database builder Run without parameters for instructions include lt stdio h gt include lt assert h gt include lt stdlib h gt include lt string h gt include interface h static void Remove_NL char x x index x Nn if x NULL x 0 X0 main int argc char argv CR_Handle handle CR_Error_Code r6 FILE x fd int count 0 if argo 3 printf build db j
205. largely irrelevant to this project However in the case of transistor models the type of transistor is very important SPICE supports many different transistor types NPN PNP and two types of JFET and MOSFET It is essential to take the type of a transistor into account during circuit matching because each type has entirely different behaviour 3 1 2 Interpreter Design Decisions The SPICE interpreter had to be easily adaptable for use by a wide variety of algorithms in particular those of Luellau and Ohlrich The algorithms could operate directly on the information in the SPICE file comparing two circuits in SPICE format directly However this would lead to a very poor design in two ways First the implementations of the algorithms would have to include code to interpret the SPICE file and this would obscure the operation of the algorithm itself In effect the source would be filled with code that had no relevance whatsoever to circuit comparison Second the code to read SPICE files would be replicated between all algorithms that made use of it Any bugs in that code would exist in at least two places and it would be difficult to make any extensions to it It is far better to have a layer of abstraction between the SPICE interpreter and all comparison algorithms This layer would consist of a circuit description format that is common to all algo rithms and the interpreter and would be simple enough to allow immediate access to all relevan
206. le argv 1 if rc CR_OK printf CR Load Database failed when loadingufromu s n t s n argv 1 CR Get Error String rc return 1 rc CR Debug amp handle if rc CR_OK printf CR_Debugyfailed s n CR Get Error String rc return 1 rc CR Free Handle handle if rc CR_OK printf CR_Free_Handle failed sin CR_Get_Error_String rc return 1 return 0 3 apps search_db c search_db c A demonstration tool that searches the database for matches for a particular circuit Run without parameters for instructions Project Source Code 10 20 30 40 60 70 80 apps search_db c 94 include lt stdio h gt include lt assert h gt include lt stdlib h gt include lt string h gt include lt string h gt include interface h include lt sys types h gt include lt unistd h gt include lt signal h gt static void Run_Search CR_Handle handle CR_Search_Type search_type const char search type str const char file name BOOL dont assume open int main int argc char argv CR Handle handle CR Error Code T ls BOOL dont_assume_open FALSE const char x db file const char x circuit file if arge 3 l Cargo 4 amp amp strcasecmp argv 1 o 0 printf search_db yja search tool for the circuitjrepository n n U
207. ling each vertex in the circuit with the number of connections running to it each vertex is labelled with a signature The signature identifies each vertex based on what is connected to it and is rather like a hashing function If the connections to a vertex are different the signature will be different Thus matching vertices can be found simply by comparing their signatures As will be explained in detail in Section this leads to a very fast matching process Luellau s method allows a subcircuit to be found within a circuit very quickly and without the need for any rules to be defined beforehand Nothing is hardwired the circuits are both general Luellau claims that the algorithm has typically near linear time complexity with the majority of circuits The method could be a significant part of the implementation of this project It will allow students to search for a part of a circuit they have drawn or to search for the circuit they have drawn as a part of a larger circuit Chapter 2 Graph Theory 11 2 4 6 The Work of Ohlrich 1993 A paper by Ohlrich T5 describes improvements to Luellau s work One significant improvement was made to signature generation Signatures now describe more of the circuit around a particular vertex they are actually based on nearby signatures As a result of this it is less probable that two or more vertices will share a signature the signature is more likely to identify a vertex uniquely Ohlric
208. listed as the best matches However users may also expect the results to be sorted by score particularly in the case of a search for 62 A Graph Matching Search Algorithm for an Electronic Circuit Repository exact matches The question of which method is better is a user interface design problem and therefore outside the scope of this project so it was decided to make the behaviour of the sort into an option Users can decide whether results should be sorted by score or by size by setting a flag in the parameters of the Search procedure It should be noted that this sort only affects the list of circuits that have been found to match Sometimes a particular circuit may be matched in several ways The list of matches within a particular circuit is still sorted by score so that the highest score appears at the head of the list In this way a user can easily find the best match involving a particular circuit Chapter 7 Evaluation 63 daVinci V2 1 empty circuit m Y Crest humor Cra amber Creat Mandar poe 2 a0 norma etras ouput sast Em sage A as Ls 2 7 3 EN i CUM ae AUT
209. longer needed Memory leaks can often go unnoticed but they can become serious problems when the program is used to solve large problems or when the program is left running The automatic test programs were executed in the Valgrind environment so that any memory handling bugs in both the circuit repository software and the test tools would be detected Valgrind detected two problems in the entire circuit repository code base One which was guickly traced to a mistake in a test tool The problem reported as Conditional jump or move depends on uninitialised value s was in the ohlrich vs luellau vs db test tool and was due to the sort by match size flag being left uninitialised This was quickly fixed The second problem was the only memory leak discovered by Valgrind It appeared in the implementation of Luellau s algorithm which is only ever used during certain tests An Edge Record object is allocated for certain connections between two vertices and then never deallocated As a result some memory is leaked by any test involving Luellau s algorithm The problem was fixed by adding code to deallocate the Edge Record objects at the end of each comparison Valgrind is no substitute for proper software engineering and testing but it is very effective at detecting subtle bugs in otherwise correctly written programs It makes a useful addition to the other test cases and provides extra confidence in the correctness of the software 7 1 3 Ma
210. move from begin p ref iter reference begin while p remove iter remove from end amp amp p ref iter reference end int ref weight p ref iter first int remove weight p remove iter first if ref weight remove weight p ref iter else if ref weight remove weight p ref iter p remove iter else remove from erase p remove iter Project Source Code D D 151 libcrdb src ohlrich circuit cc while p remove iter remove from end remove from erase p remove iter Print Partition result remove from void Ohlrich_Circuit Find_Candidate_Vector Partition partition Vertex_List amp candidate_vector 700 Partition iterator pi size_t smallest_size 70 max size_t bool found_something false assert partition empty for pi partition begin pi partition end pi 710 Vertex List current pi second size t current_size current size if found something current_size lt smallest_size candidate_vector current smallest_size current_size found_something true 720 assert found_something assert smallest size gt 0 and it wasn t an empty partition void Ohlrich_Circuit Save Item On Change List Change List change list Vertex v Change Type t Chang
211. mpty and universal circuits empty circuit 0 Circuit X 1 Circuit Y 1 2 input NAND 2 input NOR gate p34 c1 gate p14 c1 2 2 Pa _universal circuit_ 3 Hex inverters p30 c1 2 Figure 8 2 An improved version of the part of graph shown in Figure 8 1 with two dummy circuits 8 1 1 Analysis of Exploiting Dummy Circuits The addition of dummy circuits adds some overhead since both X and Y need to be examined by Ohlrich s algorithm in every search The overhead resulting from this should be much less than the work involved in examining all three real circuits if it is not then there is no point in adding the dummy circuits However as X and Y are subcircuits of the real circuits Ohlrich s algorithm will not take as long to examine them since they are guaranteed to be smaller The dummy circuit technique is only a benefit when the algorithm is searching for subcircuits of the user provided circuit because this type of search proceeds from the empty circuit to the universal circuit In order for it to be a benefit in the opposite direction dummy circuits would have to be added between the universal circuit and the real circuits That would require them to be larger than the real circuits and therefore comparisons involving them would take longer than comparisons on the real circuits themselves Therefore there would be no point in incl
212. n vli region end Vertex vertex vli if vertex gt border 530 if vertex is net debug Removed border net Ad Nn Net_Vertex vertex gt number else debug Removed borderj device As Nn Device_Vertex vertex gt name c_str Project Source Code 540 600 610 149 libcrdb src ohlrich_circuit cc remove and continue region erase vli else empty false VII 4s i if region empty p erase pi else pi return empty Ohlrich_ switch case case case case case case case case case case case assert return 1 Ohlrich_ Circuit t Get Ohlrich Weight RESISTOR return Get A Prime CAPACITOR return Get A Prime INDUCTOR return Get A Prime DIODE return Get A Prime NPN return Get A Prime PNP return Get A Prime NMOS return Get A Prime PMOS return Get A Prime NJFET return Get A Prime PJFET return Get A Prime UNKNOWN break Unrecognisedupin type Circuit Get A Prime int n Type t ao BB wne 4 5 6 8 9 11 3 12 15 16 19 20 22 23 25 This table comes direct from the original SubGemini source static const int NUMBE RPRIMES 256 1591 1523 1459 1399 1303 1237 1171 1093 1031 begin code from reference implementation
213. n needs to be exchanged between them This is a good place for an abstraction layer so an abstraction layer was introduced The interface between the two classes is as restricted as possible by Circuit_ Manager This has the side effect that Luellau s algorithm can be substituted for Ohlrich s algorithm if required but this would bring several disadvantages such as an inability to handle certain types of circuit as discussed in Section 3 2 6 However this feature may be beneficial during testing Chapter 5 Development of an Optimised Search Method 43 5 7 6 The interface for the Book Emulator In the early parts of this report it was noted that the production of any user interface for the search tool is outside the scope of the project However the tool does need to have a software interface so that the Book Emulator software can make use of it The Book Emulator is written in C so it cannot directly make use of the Database class or any other C classes objects or variables Instead a C to C interface must exist to allow access to the Database class from C Fortunately there is a high level of compatibility between C and C programs and such an interface can be written as long as the limitations of C are understood Specifically C cannot access anything that is stored as a class or part of a class It can only use more primitive types such as structs and functions in the global scope An interface was written and placed in a C
214. n about the structure of the circuit These sources do allow certain vertices to be marked as power sources but this is not useful for matching since there are many equivalent ways to connect a power source to a particular circuit For example a 5V voltage source connected between vertices 1 and 0 would be equivalent to a 5V voltage source connected between vertices 0 and 1 The basic problem is that if vertices are marked as power sources or marked as special in any way then the only possible matches for those vertices will be ones in which those vertices are marked in the same way The matching will no longer be merely structural it will be based upon vertex markings As a result no voltage or current sources are included in the graph representation Chapter 3 Evaluation of Existing Algorithms 17 3 2 Luellau s algorithm Luellau s algorithm 12 was described in a paper about a computer program called BLEX BLEX is able to take a circuit described at the transistor level and find blocks from it such as logic gates and flip flops This block extraction process is circuit matching because each block is described by a circuit fragment and BLEX must find all instances of every block in the overall circuit Neither binaries nor source code for BLEX are available but there was enough information in the paper to implement it from scratch 3 2 1 Implementation Having written the SPICE Interpreter class it was str
215. n we match those device vertices if dv gt weight dvp gt weight 690 debug Vu Comparison conflict weights are wrong Aduvsusd n dvp gt weight dv gt weight comparison_conflict true break match them dv gt assigned dvp gt assigned true dvp gt matches dv 700 dv gt matches dvp match eip and ei ei gt assigned eip gt assigned true eip gt matches ei ei gt matches eip store dvp in device stack device_stack push front dvp debug uuMatched uaddedu sutoustack Nn 710 dvp name c_str no_progress no_progress amp amp nvpl empty while device_stack empty net_stack empty amp amp comparison_conflict debug do ufinisheduwithu4ducomparisonyconflict Nn comparison_conflict 720 if no_progress Project Source Code 730 740 750 760 770 780 790 libcrdb src luellau circuit cc 138 debug do finished without making anyuprogress Mn No unique edges were found Mn return NO UNIQUE EDGES else if comparison conflict 1 return COMPARISON_CONFLICT else return OK Luellau Circuit Edge Info x Luellau Circuit Edge Record Device Vertex dev Net Vertex net Pin dev pin Edge Key ek Edge Info i ek dev dev ek net net
216. ners would recognise certain constructs and know their function Given time they would be able to determine the purpose of the entire circuit But this process requires intelligence It is not easy for a computer program to carry it out Pattern recognition techniques based upon computer vision tend to be rather fuzzy unable to give a definitive answer They also depend on the layout of the circuit on paper or on screen instead of depending only on the interconnections between the components The layout may not always be available and even when it is a circuit can usually be drawn in many different ways The output produced by two analogue circuits could be compared using a circuit simulator such as SPICE In this type of comparison a program might test two circuits with the same input signals and compare their outputs Unfortunately since the circuit is analogue the input and output voltages and currents have real numbered values There are an infinite number of possible values for each It would only be possible to test a tiny subset of the possible input values and it would be impossible in general to determine which subset of values should be used to show up differences between the two circuits Doing so would require complete understanding of the properties of any circuit which could be arbitrarily complicated Therefore this method would be either computationally intractable or unreliable in the general case Chapter 1 Introdu
217. nsorted In this specific case the properties of prime factors allow the same comparison operation to be done in O 1 time Chapter 3 Evaluation of Existing Algorithms 19 On a related note the algorithm reguires that a two dimensional matrix of edge weights be maintained for each circuit The size of this matrix is potentially very large and as Luellau notes in the paper approximately 99 75 of its elements are zero If the matrix were represented as an array 1t would be possible to find or change the value of an element in constant time However the matrix would require a large amount of space to the order of the product the number of devices and the number of connection points Another way to represent the matrix but preserve constant time access is to make use of a hash table The hashing function takes both dimensions of the matrix as its input The disadvantage of this technique is that operations on the matrix as a whole such as summing a row are very expensive Fortunately such operations are not necessary to implement Luellau s algorithm 3 2 4 Time complexity of the Algorithm The worst case time complexity of Luellau s algorithm is exponential Proof 1 Subgraph isomorphism is in N PITO 2 There is no known algorithm that can solve any problem in NP in polynomial time All problems known to be in N P require O e operations to be solved in the general case Any algorithm that could solve such a problem in polynomi
218. ntifies the prime factors that it is composed of the weight of a vertex uniquely identifies the edges connected to the vertex It is easy to tell when two vertices are not equivalent Device vertices are not equivalent if the weights are not the same a simple check for equality is sufficient to see that no match can exist In the case of net vertices the test is moderately more complex Net vertices may be open or closed as described in Section 3 1 4 A closed net vertex in the smaller of the two circuits can only be equivalent to a net vertex in the larger circuit if it has an identical set of edges connected to it So closed net vertices can be compared to possible matches in the same way as device vertices if the weights are exactly the same then the two vertices are equivalent Open net vertices are compared using another property of prime factors Because an open net vertex in the smaller circuit must have a subset of the edges of its equivalent vertex in the larger circuit the weight of the vertex in the larger circuit must be divisible by the weight of the vertex in the smaller circuit The same edges have to be present in both weights although extra edges may be present in the larger circuit The division check ensures that the edges that must be present are indeed present In general comparing the contents of two multisets to see if one multiset is a subset of the other would take O n time and even more than this if the multisets are u
219. nual Verification A number of tests were also carried out by hand using two programs that provide a simple user interface to the search tool These programs have no graphical user interface The build db program constructs a database containing a number of circuits The list of circuits to be included is taken from a text file The search db program takes a database and a circuit file and searches for the circuit within the database It prints a list of matching subcircuits and supercircuits on the standard output Using these tools a number of confidence tests were carried out by hand Manual tests have the advantage that the conditions for correctness do not need to be specified for the computer they are checked by a person instead Consequently they can involve complex conditions for correctness For example in the first test the author expected that the inverter circuit would match every NAND gate in the database In fact each inverter is a subcircuit of a NAND gate and this match will be found twice once for each input It is not easy to specify these conditions by hand However all of the tests can be run automatically once a correct set of results has been obtained and verified by hand A repeat run allows a regression test to be carried out ensuring that the software still works as it used to T he tests are run again and their output is compared with the standard diff tool to ensure that it is the same as the set of results tha
220. o apply by classifying each net vertex in each circuit by type and then sorting them into two sets for each circuit One set will be complete containing all of the net vertices for that circuit all classified by type The other set will contain only closed net vertices These sets are then used during circuit comparison to eliminate circuits that could not be related 5 4 How else can the search space be reduced In the previous sections two different tests have been described Both are suitable for cutting down the search space being based on checking that the larger circuit has a superset of the connections and the components of each subcircuit Neither can identify a matching circuit with certainty but can eliminate ones that cannot possibly match Thus they are heuristics No matter what circuits are in the database a circuit W can always be generated as the input to the search tool that will appear from the point of view of the test heuristics to match every database circuit but actually match none of them Circuit W would only need to contain enough components and enough of the possible types of connection between them This does not mean there is no point in using the heuristics In most cases they will be effective in cutting down the search space Many components and connections must be present to defeat them But it does mean that they alone will not be enough to speed up the search It would be a very bad idea to try to improve t
221. o it s not unique any more unmark push_front weight if unique 810 unmark size is guaranteed to be less than connections size so it is bounded by c for uli unmark begin uli unmark end unmark erase uli int weight uli es erase weight 820 debug Unique else debug All ifdef DEBUG debug edgesjattached to net d net gt number Print_Edge_Map es Hendif 830 void Luellau_Circuit Get_Edges Device_Vertex dev Edge_Map amp es bool unique Device_Vertex_Connection_Map_Iter cmi Weight_List unmark Weight_List_Iter uli 4 for cmi dev gt connections begin 840 cmi dev gt connections end cmi Net Vertex net cmi second Pin dev pin cmi first Edge Info x ei Edge Record dev net dev pin int weight ei gt weight f ei assigned continue v f es count weight 0 00 n o m me a mo We haven t seen any edges with this weight es weight ei operations else if unique We have seen an earlier edge with this weight so it s not unique any more 860 unmark push_front weight if unique unmark size is guaranteed to be less than connections size so it is bounded by c for uli unmark begin uli unmark
222. o supercircuits were found which is also correct given that the database contained no circuits that are supercircuits of a NAND gate Manual test 6 Test 5 was repeated but this time the value of one of the resistors in the NAND gate was changed from 1kQ to 2kQ It was expected that the comparison with the NAND gate on page 8 would cease to give a score of 1 0 and would give a score of 0 5 instead This is because one of the device values has doubled and in the scoring scheme that has been used that means that the score must be multiplied by 0 5 A was initially chosen to be 2 so the score is expected to be reduced to 0 25 The effect on the results was as predicted The score of the match was reduced to 0 25 and other match scores were also reduced by this amount whenever the altered resistor featured in the match Chapter 7 Evaluation 55 7 2 Solving the Problem of Unconnected Devices Unconnected devices slow down the operation of Ohlrich s algorithm These are devices that are part of a circuit in the sense that they are present in the SPICE file but there are no connections between them and any other devices in the circuit Unconnected devices were found during testing in one of the files in the test corpus The file described a NOR gate and it is likely that some of the devices became disconnected because of a bug in the conversion tool that was used to generate them Comparisons involving circuits that contain unconnected dev
223. o the 7404 at closed vertices Manual test 3 A Darlington pair was entered as a SPICE circuit and the database was searched The search tool correctly determined that there are no subcircuits or equivalent circuits of the Darlington pair It also correctly found the pair within several other circuits generally in the output stage However every instance of the pair that was found had connections running to all four vertices of the pair as illustrated in Figure 7 2 Le Figure 7 2 All of the instances of the Darlington pair that were found had connections to all four vertices Manual test 4 Test 3 was repeated but this time one of the vertices of the pair was closed the lower left one in Figure 7 2 This time no matches were found Because no external connection was allowed to this vertex none of the circuits found in Test 3 matched this version of the Darlington pair Manual test 5 An implementation of a NAND gate 7400 was entered into SPICE and a database search was run Five subcircuits were found all of them either NAND gates or 7404 inverters This was as expected The circuit that was entered was found to be exactly the same as one of the NAND gates in the database the one from page 8 of the Drawing Book in the Book Emulator The match scores were all 1 0 correctly indicating that the component values in each subcircuit are the same as those in the NAND gate were the same in all of the subcircuits of the NAND gate N
224. ode num ext net 480 We now read in the subcircuit as if it was part of the root circuit thus flattenning the structure String_List_Iter des_iter for des iter subcircuit gt description begin des iter subcircuit gt description end des_iter 490 char line_buffer READ_LENGTH 1 char x line_copy strcpy line buffer x des iter c str line_copy line buffer Read Device Vertex line_copy subcircuit nodes 500 bool Spice_Interpreter Directive_Is const char line const char dir return strncasecmp amp line 1 dir strlen dir 0 510 void Spice Interpreter Eat Leading Spaces char line if line NULL while isspace x line 0 assert line 0 o line 520 string Spice_Interpreter Get Word char line if line NULL return string char x token index line u 530 if token NULL token 0 N0 string s line if token NULL 540 line amp token 1 Eat_Leading_Spaces line else line NULL Project Source Code 175 libcrdb src spice_interpreter cc return s Serialisable_Signature Spice_Interpreter Get_Circuit_Signature void const const int NUMBER OF TYPES 10 560 Device Vertex List const iterator dii
225. of 1 and others have probabilities of 0 and an instance of subgraph isomorphism has been found Turner and Austin s approach is an improvement of probabilistic relaxation labelling called re laxation by elimination RBE Instead of making decisions to maximise the likelihood of a match RBE makes decisions to eliminate the least likely matches With RBE there is never any need to backtrack as there is in all of the other subgraph isomorphism algorithms that have been examined in this project 28 12 This is a major advantage of RBE which is effectively able to explore many potential instances of isomorphism matches at a time It has almost non deterministic be haviour deferring decisions for as long as possible which makes it ideal for solving the NP complete subgraph isomorphism problem On each iteration match probabilities are updated and some matches may be eliminated Updates are based upon the contextual support for each match which is a measure of how likely a match is based on the surrounding vertices For instance if A is connected to B and A has been matched to A then the level of contextual support for the match of A to A will be far higher if A is connected to some B that is matched to B with high probability When the probability of two vertices matching drops below a certain threshold they can be eliminated The actual operation of the algorithm depends on the contextual support function that is used and
226. oid int Get Luellau Weight Type t Pin p void Preparations bool reference circuit void Add Luellau Weight Device Vertex dev Net Vertex net int weight void Get Edges Net Vertex net Edge Map amp es bool unique 110 void Get Edges Device Vertex net Edge Map amp es bool unique void Get Unique Edges Device Vertex dev Edge Map amp es Get Edges dev es true void Get Unique Edges Net Vertex net Edge Map amp es Project Source Code 120 130 140 10 20 30 libcrdb include match record h 104 Get Edges net es true bool Verify Assigned Net Vertices Device Vertex dvp Device Vertex dv Deterministic Matching Result Deterministic Matching void Match Result Nondeterministic Matching void void Print Edge Map Edge Map amp es bool Test bool on Edge_Info Edge Record Device Vertex dev Net Vertex net Pin dev pin void Manipulate Flags Vertex v Flag peration Type t switch t case FINALISE finalised 1 if assigned v gt finalised v gt assigned break case CLEAR_ALL v gt finalised v gt assigned false break case CLEAR_UNFINALISED assigned 0 if not finalised v gt assigned amp v gt finalised break y void Manipulate_Flags Flag_Operation_Type t y namespace std H
227. om a net to devices struct Net Vertex Connection List Constant_Time_List lt Net_Vertex_Connection gt represents a device Project Source Code 110 120 130 140 160 170 180 libcrdb include spice interpreter h 116 class Device_Vertex public Vertex public Device_Vertex_Connection_Map connections Type type Serialisable_String model Serialisable_String name Device_Vertex matches y represents a net class Net_Vertex public Vertex public Net_Vertex_Connection_List connections Spice_Node_Number number Net Vertex x matches ds master device list used for freeing memory struct Device Vertex List Constant Time List Device Vertex gt master net list used for freeing memory struct Net Vertex List Constant Time List Net Vertex x gt Device Vertex list by type Struct Device Vertex List By Type Map std map lt Type Device Vertex List gt iterators typedef Device Vertex Connection Map iterator Device Vertex Connection Map Iter typedef Net Vertex Connection List iterator Net Vertex Connection List Iter typedef Device Vertex List iterator Device Vertex List Iter typedef Net Vertex List iterator Net Vertex List Iter typedef Device Vertex List By Type Map iterator Device Vertex List By Type Map Iter variables Device Vertex List master device list Net Vertex Connection List master connec
228. omparison although it is slightly less reliable However Daylight assert that it is effective in eliminating large numbers of molecules from consideration It is certainly the case that it will never cause a molecule to be incorrectly eliminated from consideration The fingerprinting method provides similar results to the structural keys method but no a priori decisions need to be made about which structural features are important The fingerprinting method would benefit circuit matching The technique can be copied directly by substituting devices for atoms and connection points for chemical bonds It is a good way to eliminate circuits from consideration primarily because it is fast a circuit can be eliminated in constant time and provides greater selectivity than simply examining the set of device types that are present Additionally it requires no decisions to be made at the time of database creation about the structures that are important so it will work effectively regardless of the types of circuit that are in the database Of course fingerprinting does not provide a substitute for subgraph isomorphism It can only detect when molecules or circuits cannot match However it has the potential to do this much more effectively than the techniques described in Section 5 3 particularly if the number of bits in the fingerprint hash value is large Chapter 8 Conclusions and Future Work 69 8 3 An Improved Algorithm for Searching an
229. on copy graph partition copy equiv class check failed true return Partition iterator pi 1150 Remove Diff Nodes subgraph partition copy graph partition copy Project Source Code 157 libcrdb src ohlrich circuit cc Equal sized partitions with the same labels must be marked as safe What all of the items in them But they re not matched yet match singleton partitions Now that I can understand progress false 1160 for pi subgraph partition copy begin pi subgraph partition copy end int weight pi first Vertex_List amp region pi second unsigned rsize rsize region size assert rsize 0 1170 if graph partition copy count weight 1 No match for this one pi continue Vertex_List amp super_region graph_partition_copy weight unsigned srsize 1180 srsize super_region size assert srsize 0 if srsize 1 amp amp rsize 1 Singleton partition Match Vertex subgraph_v region begin Vertex graph v 1190 x graph partition copy weight begin Save Item On Change List change list graph v Everything Save Item On Change List change list subgraph v Everything Match graph v subgraph v progress true 1200 Next item erasing this one as we go subgraph partition copy er
230. only be done once on any particular database so all circuits that are to be present in the database must be added before any call to CR Build page 81 Having built the database it can be written to disk Returns Returns CR_OK on success References See apps build db c page 91 C Interface Reference Manual CR_Create_Database 82 Synopsis CR Error Code CR Create Database CR Handle db Description Creates an empty database associated with handle db which must have been initialised beforehand The database is ready to have circuits added to it by CR Add Circuit page 80 However it is not ready to be searched or written to disk until it is built by CR Build page 81 Returns Returns CR OK on success References None C Interface Reference Manual 83 CR_Create_Handle Synopsis CR_Error_Code CR Create Handle CR Handle db Description Initialises a new handle for accessing a database Initially no database will be attached to the handle One must either be loaded with CR Load Database page 88 or created with CR Create Database page 82 Returns Returns CR OK on success References None C Interface Reference Manual CR Find 84 Synopsis CR Error Code CR Find CR Handle db CR Search Flags sf const char c file CR Result List r Description This function loads a circuit from the file specified in c file the circuit is expected to
231. onnected devices are found in a circuit a mistake has occurred Since unconnected devices slow down matching it is a good idea to make the mistake clear whenever unconnected devices are found To this end a new procedure called Test Connectedness was added to SPICE Interpreter to allow the circuit to be tested for connectedness The Build procedure was extended to call this procedure after a new circuit is added to the database and print a warning if any circuit contains unconnected devices The database will still admit circuits containing unconnected devices but a warning will be issued for each during the database build process The operation of Test_Connectedness is quite simple A vertex V is chosen from all of those present in the circuit Then a recursive procedure is called with V as a parameter It sets a connected flag on V to TRUE then tests all the neighbours of V If any neighbour V does not have the connected flag set to TRUE the recursive procedure is called again with V as a parameter After all the recursive procedures have returned all vertices should have the connected flag set to TRUE If any vertex does not then it is not connected to the original vertex V and the circuit is not fully connected V may well be an unconnected device itself so it is unhelpful to list all of the vertices that are not connected to it Instead one example of two vertices with no connection between them is given This will aid the user o
232. or dli master_device_list begin dli master_device_list end dli gt connected false for nli master_net_list begin end O Device Vertex v end O string amp output dli Project Source Code String To Type Serialisable_String amp s const D D i i libcrdb src spice_interpreter cc 180 930 nli master net list end nli nli gt connected false assert master net list empty prepare output nli master net list begin output net Int To String nli number and 940 begin recursion Test Net Connectedness nli scan for unconnected vertexes for dli master device list begin dli master device list end dli if dli connected output output device dli gt name 950 return false for nli master net list begin nli master net list end nli if nli connected output output net Int To String nli gt number 960 return false output ok return true Spice Interpreter Net Vertex x Spice Interpreter Get Spice Node Spice Node Number nn 970 Spice Node Map amp node_map if node map count nn 0 No not seen before Net Vertex new node new Net Vertex
233. ouble the time taken by the algorithm If z is 2 then the time taken will approximately be squared Corneil stated that for certain types of graph his algorithm could detect graph isomorphism in O n time The value of the growth factor 2 for his algorithm was 5 in those circumstances While this may seem like a high level of growth the problem is still considered to be computationally tractable because the growth is not exponential Developing the work of Corneil Ullmann 28 described an algorithm to solve the subgraph isomorphism problem The speed of his algorithm however was limited by the fact that the general subgraph isomorphism problem is known 10 to be NP complete NP complete problems are ones that are known to be solvable in polynomial time provided that a non deterministic computer is available Provided that a computer can guess a correct answer to an NP complete problem that guess can be verified in a very short period of time A non deterministic computer could try all possible guesses in an instant and thus the only time taken to solve the problem would be the time taken to verify that a guess was correct Of course such computers are not possible or at least they are not Turing machines In practice this behaviour can only be simulated by trying each guess in sequence If there is a need to choose one of x values for each of y variables then the process will take at least x steps The growth factor is exponent
234. pe switch st case CR SEARCH FOR SUBCIRCUIT db sf search type Database SEARCH FOR SUBCIRCUIT 190 break case CR SEARCH FOR SUPERCIRCUIT db sf search type Database SEARCH FOR SUPERCIRCUIT break case CR SEARCH FOR EQUIVALENT db sf search type Database SEARCH FOR EQUIVALENT break default return CR UNSUPPORTED SEARCH TYPE 200 db_sf dont_assume_open sf gt dont_assume_open FALSE db sf only_find_first_match sf gt only find first match FALSE db sf sort by match size sf sort by match size FALSE Read the circuit try Then attempt to search for it Serialisable Circuit Record circuit Serialisable Circuit Record string c file 210 ptr db gt Search circuit db sf db results catch const char ex Convert the results from Search_Result_List type to CR_Result_List type return Translate_Exception ex Project Source Code 220 230 240 260 270 280 290 src interface cc 184 try Database Match Record List iterato Match Record Device Match List iterator k Match Record Net Match List iterator 1 CR Result List x i db results end while i db results Database Search Result Record amp Serialisable Circuit Record amp CR Result List CR Match List x previous match OL copy the basic information
235. ph isomorphism algorithms to the problem will make the search tool reliable and able to operate on any analogue circuit If an optimised algorithm is used the search tool can be very efficient These are features that no other method of circuit comparison can offer and this is why this method of comparison was chosen A Graph Matching Search Algorithm for an Electronic Circuit Repository Chapter 2 Graph Theory Comparing circuits is a type of subgraph isomorphism problem An electronic circuit is easily expressed as a graph an example of one possible representation was illustrated earlier in Figure Since this is the case existing methods for solving subgraph isomorphism problems can be applied to comparing circuits In this chapter research into graph theory and the problem of graph isomorphism will be examined Graph isomorphism is a special case of subgraph isomorphism in which the two graphs have the same number of vertices and edges This will be followed by an examination of subgraph isomorphism problems and their complexity Then the existing research into circuit comparison will be investigated 2 1 What is graph isomorphism The dictionary 16 definition of an isomorph is a substance having the same form or composition as another Two graphs are isomorphic if they have the same structure an equal number of vertices linked by an identical edge structure The two graphs in Figure 2 1 are isomorphic Simply by moving the
236. ponents and connection points are vertices of a graph Figure illustrates an electronic circuit expressed as a multiplace graph as described by Ablasser Some of the device vertices net vertices and edges have been indicated as such i z device vertices edges WAR R3 1k net vertices a ali Figure 2 3 A circuit expressed as a multiplace graph The method of detecting isomorphism is highly optimised The graphs are reduced to adjacency matrices with each cell containing the number of connections between a particular node and spider The matrices for two isomorphic graphs A and B will have the same cells but the order of the rows and columns of the matrix for B will be a permutation of those for A The algorithm attempts to determine the mapping of vertices from A to B If a total mapping exists then the two graphs are isomorphic Exhaustively testing each permutation would be very time consuming so Ablasser s algorithm labels the edges of the graphs with their type This is simply their function in the original circuit An edge leading from a transistor might be labelled as base or collector Adding this information to the matrices simplifies the problem of mapping A to B Thus Ablasser s method is able to detect when two circuits have the same structure This is Chapter 2 Graph Theory 9 perhaps of some use to a student students could draw part of a circuit and then find a circuit f
237. put procedures Secondly it is stated on a University of Washington website that the SubGemini program exists only as a prototype 5 Since it was never considered to be finished the reliability of the code is questionable particularly as this project would apply SubGemini in a way that it was not intended to be used which might unearth bugs that were not found by the original authors 3 3 2 Implementation A new class called Ohlrich Circuit was written This inherited from SPICE Interpreter adding a Compare To function just like the Luellau Circuit class 3 3 3 Differences between the Algorithms Ohlrich s algorithm is very similar to Luellau s algorithm It operates in two phases during the first a key vertex is chosen from the smaller graph and a list of possible matches for that vertex is found in the larger graph This list is called the candidate vector This is done by labelling every vertex in both circuits with a label that identifies its type and the number of connections to it In the second phase the algorithm makes a tentative match between the key vertex and one of the vertices in the candidate vector This match is used as a starting point for a gradual match of the entire circuit The gradual matching process is very similar to the process used by Luellau s algorithm which was illustrated in Figure However a number of improvements have been made First the method by which the starting point is found is
238. r It is possible that the authors of the original implementation did not consider the use of red black trees or any other type of balanced tree because of the difficulty of implementing them Although simple trees are easy to implement balanced trees require a great deal of implementation and testing work However because red black trees are provided as an abstract data type ADT by the STL 14 they can be used in this project without any difficulty 4 2 A Disadvantage of the STL Linked List Type During implementation of Ohlrich s algorithm the STL linked list type list was used whenever appropriate In this implementation linked lists are used for storing lists of vertices and connections and for returning results Generally they have been used wherever there is a need to store a variable number of items that are only accessed sequentially One shortcoming of the STL linked list type is that obtaining the number of elements in the list is not guaranteed to be a constant time operation A function called size is provided which returns the length of the list but the time complexity of this operation may be linear The implementors of the STL list type are free to choose how size is implemented In some versions of the STL such as the SGI version it is implemented by counting every element in the list This is a simple but very inefficient implementation which slows down all code that makes use of size There is no need for size
239. ragment that matched it in the database However Ablasser s method would only find a match if the two had identical structure Thus the student s drawing could not feature any additional components even if those extra components were irrelevant to the circuit s function A tool based on Ablasser s method alone could be frustrating to a student because of the requirement for exactness 2 4 2 The Work of Spickelmier et al 1985 Spickelmier 18 suggests an alternative approach to that used by Ablasser His work was also intended for the verification of mask artwork against an original circuit Spickelmier notes that methods such as Ablasser s depend on the properties of a circuit at a local level In Ablasser s method two components were matched by comparing their connections But this is not ideal because it is quite possible that a large number of components may not be distinguishable by this method The only way to find the correct match would be to try them all which could be computationally expensive Spickelmier suggests that a rule based system could be used to match the circuits Rule based systems have applications in artificial intelligence they make inferences based on some inputs and a large list of logical rules Spickelmier has applied an existing rule based system to solve the comparison problem OPS5 8 and written a program to generate the rules from the circuit The output produced is as follows First each functional block
240. raph isomorphism algorithm can also be used to detect graph isomorphism The first of these is likely to be the most useful One can imagine that for user friendliness the list of subcircuits might be restricted to those involving certain user selected components Figure 2 4 shows a possible sequence of events Darlington Pair i Arranging two transistors in this way gives a much higher current gain than either transistor alone The total current gain is egual to the product of the current gain of each transistor 1 2 3 Figure 2 4 An example of a search The student draws a Darlington pair as part of a larger circuit 1 Wishing to learn about this part of the circuit the student clicks on one of the transistors in the pair which becomes highlighted 2 A database search then reveals all of the database circuits that are a subcircuit of the entire circuit and include the selected transistor with the same connections There is only one such circuit the Darlington pair This result is displayed 3 With the addition of an additional procedure to compare the component value associated with each device additional types of search will become possible Some devices have values associated with them such as resistance in the case of a resistor and it will become possible to insist that 12 A Graph Matching Search Algorithm for an Electronic Circuit Repository any
241. re will be discussed in a later chapter Chapter 3 Evaluation of Existing Algorithms In the previous chapter it was stated that Luellau s algorithm could be used as the core of the search tool Ohlrich s algorithm could also be used These are not necessarily the most efficient algorithms for a search within a database but implementing them helps the author to gain useful insight into how they operate In addition the implementations form the basis for the search tool and the test tools that were developed for it 3 1 Groundwork No matter how circuit comparison is carried out the circuit structure that is used will come from a circuit description in SPICE 30 format All of the algorithms will need to be able to interpret the SPICE format which will now be examined 3 1 1 The SPICE File Format SPICE files are human readable text files in which each line is called a card There are three types which can be divided into control cards containing commands element cards describing electronic devices and comment cards The circuit illustrated in Figure 1 is described by the SPICE file in Figure gt TT 7 RI R2 R4 4k 1k6 130 6 Q3 5 D1 8 Q4 O N Q2 109 R3 Ik 2 4 0 Figure 3 1 An inverter circuit 13 pl A A Graph Matching Search Algorithm for an Electronic Circuit Repository Inverter 7404 WIDTH IN 72
242. rence Vertex v E std pair lt int Net Vertex List k1 std pair lt int Net Vertex List k2 std pair lt int evice_Vertex_List gt d pai int D i V Li ki std pair lt int Device_Vertex_List gt k2 107 libcrdb include serialisable h class Scored_Circuit public Ohlrich_ Circuit public Scored Circuit istream amp fd Ohlrich Circuit fd Scored Circuit Ohlrich Circuit virtual Scored Circuit int Compare To Scored Circuit kt Match Record List amp mrl bool assume all open true bool only find one match false bool sort by size false protected virtual void Build Match Record Spice Interpreter that private struct Sort By Score bool operator const Match Record amp x const Match Record amp y const return x score gt y score ys struct Sort_By_Size bool operator const Match Record amp x const Match Record amp y const return x device_matches size x net matches size gt y device_matches size y net matches size F3 double Get_Value Device_Vertex v D 13 libcrdb include serialisable h ifndef SERIALISABLE_H define SERIALISABLE_H include lt iostream gt include lt fstream gt include lt map gt namespace std class Serialisable public Serialisable virtual Serialisable virtu
243. rences into account so it may be necessary to try different values for A 6 2 Implementation It was decided that scoring would be best implemented by extending the class that implements Ohlrich s algorithm since this allows new functionality to be added without changing any of the existing code or the test cases that ensure it operates correctly It is important that existing code and test cases do not need to be rewritten to any extent unless it is absolutely necessary since bugs may be introduced 48 A Graph Matching Search Algorithm for an Electronic Circuit Repository The Ohlrich Circuit class was extended by a new class called Scored Circuit This new class provides the same features but every search result includes a score and all results are sorted in descending order of score A score is assigned to each match between two circuits There may be more than one match between two circuits so a score is given to each one The list of matches is sorted so that the best score is at the head of the list This information is then handled by the Database class using a simple extension to the Search procedure The results output by the Search procedure are sorted so that the circuit that is the closest match is at the head of the list The score that is assigned to each match is available to the user of the search through a field in the CR Match_List This allows some indication of the rank of each match to be displayed by the user inter
244. resentation of the difference 1 1kQ is 92 of 1 2kQ but 100 is only 9 of 1100 The larger a difference is the more significant it becomes To represent this a power law approach can be used Here each difference is raised to some power A after calculation by the division described in the previous paragraph The incorrectness function x y defined below indicates how close the values of device vertices x and y are to each other Let Vx be the set of device vertices in X and Vy be the set of device vertices in Y v x is the value assigned to vertex x The function f is the isomorphism function determined by Ohlrich s algorithm so f x is the device in Vy that is equivalent to x Vx The following equations give the value of x y Va e Vx y E Vy y f x v x gt v y gt i z y v y 6 1 v x v x Ne Vx Vx y Vy y f x v z lt v y gt i z y 6 2 v y This function gives the difference between two values x y has the range 0 1 since device values cannot be negative It is equal to 1 if there is no difference between the vertex values an exact match gives the highest result The function is also symmetric i z y y x The overall score score X Y is the product of the values of i z y The effectiveness of this scoring approach will be examined in the Evaluation chapter The scoring will be more discriminatory with higher values of A taking larger diffe
245. rialisable list h ifndef SERIALISABLE LIST H define SERIALISABLE LIST H include serialisable h include constant time list h namespace std 10 template lt typename _Tp typename _Alloc allocator lt _Tp gt gt class Serialisable_List public Constant_Time_List lt _Tp _Alloc gt public Serialisable public Serialisable List Constant_Time_List lt _Tp Alloc 20 bool Write std ofstream amp out const typedef typename list lt _Tp _Alloc gt const_iterator IV IV i Begin by writing the size of the list if Write_Integer out size 30 1 return false Then write out each element for i this gt begin i this gt end i if x i Write out return false 40 return true a bool Read std ifstream amp in int read_size int i 3 50 if Read Integer in read size return false clear for i 0 i lt read_size i _Tp new_item 60 if new item Read in return false insert end new_item return true jus 7 0 namespace std endif Project Source Code 10 20 30 40 60 70 111 libcrdb include serialisable map h D 17 libcrdb include serialisable map h ifndef SERIALISABLE MAP H define SERIALISABLE_MAP_H include lt map gt include serialisable h namespace std template class _Key class
246. rialisation test cc This program first ensures that primitive data types such as strings and integers can be serialised and deserialised correctly It then ensures that the contents of a database are undamaged by serialisation Finally it checks that each circuit can be serialised and deserialised without information loss by comparing two versions of each circuit in a test corpus One version has been serialised then deserialised and the other has been read directly from a SPICE file The two should be identical and the test ensures this Permutation Test It is important that the order of the devices in the SPICE file has no effect on the comparison algorithm because devices may be listed in any order in a SPICE file In order to verify this a test program called random order test c was written This test program takes each circuit file in the corpus and repeatedly shuffles the order of the SPICE element cards within it to produce new versions of the circuit These circuits are then tested for isomorphism The test fails if two circuits are found not to be isomorphic or if the matching procedure is unable to find the correct correspondence between the devices and nets in the circuits The permutation test did not find any circuits which ceased to be isomorphic after the device order was randomised However it did reveal a bug in the implementation of Ohlrich s algorithm in which the order of devices became important in certain circuits becaus
247. roject does not involve any user interface design It is up to others to integrate the work done during the project with the Book Emulator user interface The project is concerned only with the development of the search tool and the repository builder deciding which search functions will be useful determining optimal implementations for them and finally implementing them The implementation must provide the required functions in such a way that they are ready for integration into generic software Furthermore the project does not involve the entry of information into the circuit repository A test circuit repository will need to be produced for evaluation purposes but the one that will be available to the final end user is expected to be produced by others 1 4 The difficulty of circuit comparison The project requires an algorithm capable of comparing two circuits It may need to search thou sands of circuits so it must be as efficient as possible Furthermore it must correctly find any sort of analogue circuit not merely all of those with particular properties since it is impossible to know every circuit that may be added to the repository in the future or indeed the circuits that will be searched for It is not easy for a computer to determine the function of an analogue circuit A computer can be given access to every aspect of a circuit that a human would be able to see component values interconnections perhaps even component location
248. s void Database Make_Link Circuit_Number sub_number Circuit_Number super_number Serialisable_Circuit_Record amp sub db sub number cr Serialisable Circuit Record super db super number cr if sub number super number super Is Signature Subset sub return Project Source Code libcrdb src database cc 120 Match Record List mrl Edge Degree degree Edge Degree super Is Subcircuit sub mrl true false false 60 if degree gt 0 sub is a subcircuit of super with the given degree and super is a supercircuit of sub Before we add the link make sure that no link exists in the opposite direction if db sub number subs count super number gt 0 A link in the opposite direction was found 70 This means that super and sub are eguivalent each is a subcircuit of the other For now we print a message and keep only one of the links cout lt lt EQUIVALENCE between lt lt sub Get Circuit Name lt lt pandu lt lt super Get Circuit Name lt lt An else db super_number subs sub_number degree db sub_number supers super_number degree 80 H bool Database Is_Link_Between Circuit_Number sub_number Circuit_Number super_number Circuit_Map iterator child Search for direct links 90 for child db sub_number supers begin
249. s algorithm needs to find a starting point to begin analysis of a circuit The starting point will be the vertex with the maximum number of unique edges edges with a weight that does not appear elsewhere in the circuit Unfortunately some circuits have no such edges A very simple example of such a circuit is shown in Figure 3 5 In this circuit there are two edges between a and b and b and c but the edges cannot be distinguished As a result Luellau s algorithm cannot find a point in the circuit to start matching and always fails Luellau s paper does not define what should be done in this situation The algorithm can easily be modified to report an inconclusive result if this situation arises but this is not very useful in a search tool that is supposed to find exact instances of subgraph isomorphism 1 To find the maximum value of x let a 2 1 Taking the logarithm of both sides x log a log 2 1 _ log 227 1 _ log 2 1 2218 Then x k s log 39 3367 6 58 Thus in practice x lt 6 Chapter 3 Evaluation of Existing Algorithms 21 b RI 1k Figure 3 5 Luellau s algorithm cannot find any supercircuit for this circuit because none of the three vertices marked a b and c have unique edges 3 3 Ohlrich s algorithm Ohlrich s algorithm 15 is the main part of a system called SubGemini which is able to find instances of a circuit within another circuit Unlike
250. s are discussed 6 1 1 The source of device values The device value information can be found in the SPICE file Every element card which describes a device has a field on it which gives the value of the device For example the following line of SPICE describes a 2 2kQ resistor called R1 which links nets 5 and 6 R1 5 6 2 2K Reading the value information from the SPICE file presents no difficulty The SPICE Inter preter class was extended to read the value into a string which is stored as part of the information for every device However interpreting the value is a little more difficult The rules used by SPICE to interpret values must be applied It was decided to interpret the device values assigned to capacitors resistors and inductors in their entirety To do this all the possible ways that the values could be described to SPICE must be understood SPICE accepts device values in engineering form in which suffixes including K kilo U micro and N nano are accepted as scale factors for the value of the device It also accepts values in the 45 46 A Graph Matching Search Algorithm for an Electronic Circuit Repository standard scientific form where an exponent is given If no exponent or scale factor is given the scale factor is assumed to be 1 Thus 1000 1K and 1E3 are all interpreted as the same number It was decided to ignore the device values assigned to transistors and diodes These values specify the mod
251. s so that the circuit can be drawn on screen However a computer cannot interpret this information as easily as an experienced engineer There are some circuits that are easily compared Digital circuits are a special type of analogue circuit It is not difficult for a computer to examine a combinatorial digital circuit A computer can always work out the minimum logical function that such a circuit provides and compute truth tables This type of circuit has discrete inputs and outputs each of which can only take two values Combinatorial circuits can thus be compared in terms of the minimal representation of their logical function or in terms of their truth tables However this is not possible for non combinatorial digital circuits those with some type of memory or internal state A logical function or truth table could only be drawn for such circuits if its parameters included all the values of the internal state In an analogue circuit a truth table can never be derived because all inputs and outputs have real values Voltage and current are continuous quantities which may take any real numbered value Nor is it possible in general to reduce an analogue circuit to a mathematical function which could be compared more easily Analogue circuits may have internal state and may be arbitrarily complicated So a computer must use some other method to compare analogue circuits Humans would do the task by pattern recognition Experienced circuit desig
252. safe border false connected false y int weight bool finalised bool open bool is_net bool assigned safe border bool connected y class Spice_Interpreter public Serialisable public represents a device type enum Type DIODE RESISTOR CAPACITOR INDUCTOR NPN PNP NMOS PMOS NJFET PJFET UNKNOWN represents a device pin number typedef unsigned Pin public functions Spice Interpreter istream amp fd Serialisable Read Spice File fd y Spice Interpreter Serialisable virtual Spice Interpreter for information about the circuit string Get Circuit Name void const return circuit name Serialisable Signature Get Circuit Signature void const for serialisation bool Write std ofstream amp out const bool Read std ifstream amp in void Debug void const bool Contains Closed Net Vertices void const bool Test Connectedness string amp output protected class Device Vertex class Net Vertex A Spice node number typedef int Spice Node Number represents a list of connections from a device to nets struct Device Vertex Connection Map std map lt Pin Net Vertex gt represents a connection from a net to a device struct Net Vertex Connection Pin device pin Device Vertex x device ys represents a list of connections fr
253. sage search_db 0 lt database file name gt lt circuityfile gt n n The specified database is searched for the specified circuit n The resultsjofjany match are printed to the standard joutput n Ityisyjyoftenya good idea to pipe the output through more 1 n n By default this tool assumes thatjall vertexes are open Toyturn n this off add the o parameter to the command line n n return 1 if argc 3 dont_assume_open FALSE db file argv 1 circuit file argv 2 else dont assume open TRUE db file argv 2 circuit file argv 3 rc CR_Create_Handle amp handle if rc CR_0K printf CR_Create_Handleyfailed 4s n CR_Get_Error_String rc return 1 rc CR_Load_Database amp handle db_file if rc CR_0K printf CR_Load_Database failed when loading from s n t s n db file CR_Get_Error_String rc return 1 Run_Search amp handle CR_SEARCH_FOR_SUBCIRCUIT subcircuit circuit_file dont_assume_open Run_Search amp handle CR_SEARCH_FOR_EQUIVALENT equivalent circuit_file dont_assume_open Project Source Code 90 100 110 120 130 140 160 95 apps search_db c Run_Sear printf ro COR if rc 1 prin ch amp handle CR_SEARCH_FOR_SUPERCIRCUIT supercircuit circuit file dont assume open An
254. scribed here Section discussed the use of two types of trivial test to eliminate circuits that could not possibly be matches In the implementation code was only written to carry out the tests involving the numbers of particular components Ohlrich s algorithm performs equivalent tests to those described in Section 5 3 during the first phase of its operation and will stop immediately if any fail The interface and database library are thread safe provided that no two database operations take place on the same object at the same time This means that any number of database operations can take place simultaneously provided that each has a different handle 44 A Graph Matching Search Algorithm for an Electronic Circuit Repository There is still an advantage to comparing the numbers of components in the circuits before Ohlrich s algorithm is applied because it can be done from a database table without any need to load in the SPICE circuit But there is little advantage to comparing the types of connection point present since the first part of Ohlrich s algorithm does this effectively Specifically the equivalent tests in Ohlrich s algorithm already work around the open vertices problem described in Section 9 9 2 Section discussed the possibility that circuits might be stored in a prepared form in the database This would remove the need to translate circuits from SPICE format before each com parison and remove the need to assign an initi
255. se and average case performance of Ohlrich s 10000 250 300 comparison time drawn using data gath 1000 100 0 1 fi fi l fi T Worst case time bound Average case time bound 0 50 100 150 200 Number of Devices in Supercircuit data gathered from 12 010 random circuit comparisons 250 300 algorithm based upon the 60 A Graph Matching Search Algorithm for an Electronic Circuit Repository Cases 7 3 2 The Usefulness of the Search Tool Clearly a search tool is only effective if it is useful to the end user The features of the search tool will be reviewed in this section from a user perspective e Feature 1 Exact matching An exact match of a user provided circuit can be found in the database automatically An exact match will have the same structure and the same component values and thus it will appear in a results list with a score of 1 0 To perform this type of search one would call the CR Find procedure with a search type of CR SEARCH FOR EQUIVALENT and ignore all results with a score other than 1 0 e Feature 2 Structural matching A structural match an isomorph of a user provided circuit can be found in the database automatically This will have the same structure but may have different component values so the score will not necessarily be 1 0 To perform this type of search one would call the CR Find procedure with a search type of CR SEARCH FOR EQUIVALENT
256. sitory The test also involved only randomly generated circuits These circuits are generally electronic gibberish The reader may question how a test using only this type of circuit could have any relevance to an algorithm that in practice will be used on real circuits The answer is twofold first random circuits provide pathological examples of unstructured circuits that are difficult to match Second any useful circuit will be generated by a random process given sufficient time It is almost certain that some practical circuits were generated and tested during the test run 3 4 Conclusions At this point it is clear that Ohlrich s algorithm is superior to Luellau s Three of the most important advantages are e Luellau s algorithm cannot handle every circuit For example it cannot find supercircuits of Figure Ohlrich s algorithm appears to be able to handle all circuits according to the testing that has been performed by the author and the claims of the algorithm s designers e Ohlrich s algorithm consistently chooses either the same starting point as Luellau s algorithm or a better one resulting in a smaller candidate vector e Ohlrich s algorithm is not subject to any limitation on the number of vertices that may be connected together whereas the reliance on prime factors in Luellau s algorithm causes a problem when large numbers of vertices are connected The search tool that was implemented is based upon Ohlrich s algorithm
257. ss two for device definitions iter device definitions begin device definitions iter device definitions end device definitions iter char des buffer READ LENGTH 1 120 strcpy des buffer device definitions iter c str Read Device Vertex des buffer toplevel node map Free up the temporary space used for subcircuits Spice Subcircuit Map Iter ssmi 130 for ssmi spice subcircuits begin ssmi spice subcircuits end ssmi delete ssmi second Remove node 0 if nothing is connected to it Node O is global and it is generated whenever any subcircuit is used regardless of whether or not the subcircuit uses it However having an unconnected node is bad so 140 Net Vertex node0 Get Spice Node 0 toplevel node map if node0 gt connections empty delete it from the master node list Net Vertex List iterator nli for nli master net list begin nli master net list end nli 150 Net Vertex nv nli if nv node0 master net list erase nli break delete it from the node map Project Source Code libcrdb src spice_interpreter cc 170 160 toplevel_node_map erase 0 delete node debug Removed unused node O n Make all top level nodes open Spice_Node_Map iterator snmi for snmi toplevel_node_map begin snmi
258. sure that the match does not depend on assuming that those vertices are open Thus the correctness of the results can be preserved 5 6 Improving the part of graph approach The part of graph approach provides a fast way to search the database The algorithm uses pre computed information about the relationships between the circuits in the database to eliminate circuits from consideration as soon as possible It can also apply trivial tests to eliminate circuits that cannot possibly match such as those described in Section 5 3 It has been claimed that the part of graph approach is optimised But is it the best possible approach Suppose that the search algorithm is being used to find all subcircuits of X that are present in the database T he set of subcircuits of X in the database is R The set of circuits that are tested by the search algorithm is T Ideally T R that is the algorithm only tests the circuits that are actually subcircuits of X However this is not generally possible The algorithm cannot know which circuits to choose in advance Because of step no circuit is tested more than once Therefore the number of comparisons carried out by the algorithm can be no more than the number of circuits in the database In addition to this no circuit is tested if any evidence has been found that shows it cannot be a subcircuit of X The algorithm makes use of the only reliable information that is available for this purpose the results of
259. t 1 2 The environment of the search tool 13 Scopeoftheproject aa 1 4 The difficulty of circuit comparison re 2 Graph Theory 2 What is graph isomorphism 2 2 What is subgraph isomorphism 2 3 The Complexity of the Problem ooo 2 4 Research into Circuit Matching 2 4 1 The Work of Ablasser and J ger 1981 2 4 2 The Work of Spickelmier et al 1985 2 4 3 The Work of Takashima et al 1988 2 4 4 Consolidation 2222s 2 4 5 The Work of Luellau 1984 LL 2 4 6 The Work of Ohlrich 1993 a 2 5 The best direction to take 3 Evaluation of Existing Algorithms 3 1 Groundwork 3 1 1 The SPICE File Format 3 1 2 Interpreter Design Decisions ees 3 1 3 A choice of languages ss 3 1 4 Implementing the SPICE Interpreter 3 2 Luellau s algorithm 3 2 1 Implementation Mu a V S cum Ss su a eee wx SES NM E a AAA 3 3 1 Reimplement or not 3 3 2 Implementation 3 3 3 Differences between the Algorithms llle 3 3 4 Testing the implementation a 3 4 Conclusions 4 Improvements to Ohlrich s comparison algorithm 4 1 Hash tables or red black trees 4 2 A Disadvantage of the STL Linked List Type leen 4 3 Prepared circuits ORE SE OO WONN DH ore Ex qu m js ere oo O 13 13 13 14 15 15 17 17 17 18 19 19 20 21 21 21 21 23 24 TABLE OF CONTENTS TABLE OF CONTENTS 5 Development of an Optimised Search Me
260. t The same test tool could be reused since both classes present the same interface to other parts of a program It was only necessary to substitute Ohlrich for Luellau in the test procedure In addition some new tests were possible The two algorithms should produce the same answer when asked to compare any two circuits so a second test tool was written to take advantage of this The tool worked from a corpus of 27 circuits most of which were extracted directly from the Book Emulator 3 using a tool developed by Keffin Barnaby as part of his project 2 Other circuits were entered by hand The test tool selected every possible pair of circuits from the corpus and ran the two algorithms on them The results of the comparison given by both algorithms had to be the same if it didn t the test halted with an error And if a circuit was being compared to itself an autocomparison then both algorithms had to report a match During testing it was found that some of the circuits in the corpus caused Luellau s algorithm to terminate with an error due to the unique edges problem described in Section 3 2 6 The algorithm had not been able to find any unique edges so it was not able to carry out any comparison The results of these tests had to be discarded however only a minority of tests ended in this way The implementation was also tested by a random stress test called breakdown cc In this test a circuit was generated at random by a
261. t begin i this end i 80 1 const std pairc Key _Tp gt amp item x i if i this gt begin stdricolt lt lt y std cout lt lt item first Debug std cout lt lt 90 item second Debug std cout lt lt y y namespace std endif D 18 libcrdb include serialisable_set h ifndef SERIALISABLE_SET_H define SERIALISABLE_SET_H include set include serialisable h namespace std 10 template lt class _Key class _Compare std less lt _Key gt class _Alloc std allocator lt _Key gt gt class Serialisable_Set public std set lt _Key _Compare _Alloc gt public Serialisable public Serialisable Set std set lt _Key _Compare Alloc 20 bool Write std ofstream amp out const typedef typename std set lt _Key _Compare _Alloc gt const_iterator IV IV i Begin by writing the size of the set if Write_Integer out size 30 1 return false Then write out each element for i this gt begin i this gt end i if x i Write out return false 40 return true y bool Read std ifstream amp in Project Source Code 113 libcrdb include serialisable_signature h unsigned read_size unsigned i 3 50 if Read Integer in read size return false clear for i 0 i lt rea
262. t information It is this approach that was chosen because of the clear advantages it brings Comparison code can be more readable and all code involved with reading SPICE files is in one place It also brings the advantage that circuits can be stored on disk in other formats which proved to be very useful once a serialisation feature was added to allow circuits to be stored within the database Chapter 3 Evaluation of Existing Algorithms 15 3 1 3 A choice of languages Since the Book Emulator is written in C the programming languages available for implementing the search tool are C and its superset language C The C language was chosen for three reasons Firstly the language supports inheritance So an algorithm can be made to use a generic interpreter class just by inheriting it This provides a framework for the abstraction layer between the interpreter and the algorithm Secondly the language supports a library of abstract data types known as STL the Standard Template Library 14 These types which include sets hashes and binary heaps make it easy to implement any algorithm efficiently and correctly They were heavily used in the implementation of the search tool Finally the language includes several features that make it easier to write correct code none of which are available in C C is strongly typed so bugs are not normally introduced by type conversions A reference type is available which provides a safe alternative
263. t are known to be correct A regression test suite is included with the software produced for this project The following section describes the tests that were carried out and their results Manual test 1 A 7404 inverter was entered as a SPICE circuit and the database was searched for similar circuits with the assumption that all vertices were open The author expected to see exact matches for all of the inverters in the database and this was indeed seen in the output of search db The 7404 was also expected to be a subcircuit of all the NAND gates in the database Two unexpected matches were found They were found to be correct after examination of the circuit structures involved First it was found that the high speed NAND gates in the database are not supercircuits of the 7404 This is because their circuits are quite different Second it was found that one NOR gate taken from page 14 in the Book Emulator Drawing Book is a supercircuit of the 7404 54 A Graph Matching Search Algorithm for an Electronic Circuit Repository Manual test 2 Test 1 was repeated but without the assumption that all vertices were open The only open vertices in the 7404 inverter were the power rail ground input and output vertices The result was that the only circuits found were those that exactly matched the 7404 This is a correct result given the results of the first test because all of the other circuits that were found in Test 1 added extensions t
264. t vertex OL starting device vertex OL operations 0 Luellau Circuit Luellau Circuit Project Source Code end O D rmi 129 libcrdb src luellau circuit cc 30 DA void Luellau_Circuit Preparations bool reference_circuit assert prepared prepared true 40 Device_Vertex_List_Iter dli Net_Vertex_List_Iter nli debug Begin preparationsuyforuy s u 4s n circuit_name c_str reference circuit Reference Other Calculate the weight of each device 50 for dli master device list begin dli master device list end dli Device_Vertex comp dli comp gt weight 1 Device_Vertex_Connection_Map_Iter cmi for cmi comp gt connections begin 60 cmi comp gt connections end cmi Pin pin cmi first comp gt weight Get_Luellau_Weight comp gt type pin debug Component suweight 4d n comp gt name c_str comp gt weight 70 device list by weight comp gt weight push_front comp And the weight of each net for nli master net list begin nli master net list end nli Net_Vertex net nli 80 net gt weight 1 Net_Vertex_Connection_List_Iter cli for cli net gt connections begin cli net gt connections end cli
265. t would be possible to 1 Find any subcircuit of the student s circuit that might exist in a database thus identifying the subcircuits 2 Find a circuit in the database which is a supercircuit of the student s circuit 3 Find any circuit in the database with the same structure as the student s circuit 5 2 Assumptions In the following sections it is assumed that a database of circuits is prepared before any searches take place It is important that searches are as fast as possible so the database can and should contain whatever is needed to speed up the search General purpose SQL databases always maintain indexes and hash tables to allow fast access to data Speed of database preparation is not an issue because unlike searching preparation is an oc casional task The preparation task must complete in a reasonable amount of time taking a minute would be acceptable but taking a day would not 5 3 Trivial tests The database may have an arbitrarily large number of circuits within it so if some can be eliminated from the search process early on the speed of the search can be vastly increased There are some simple tests that can detect when circuits cannot possibly match They can only prove the negative saying either that these circuits cannot match or these circuits may match However this is useful they cut down the number of circuits that need to be examined by the algorithm that can say for certain wh
266. tch Items cr items new CR Match Items cr items gt subcircuit item C String subcircuit net cr items gt supercircuit item C String supercircuit net cr items gt type CR NET cr items next previous items cr items previous items cr_match gt items cr_match gt score cr_record gt match_lis t previous_items match_record score previous_match Project Source Code Viva circuit D 185 src interface cc r previous_record catch 300 return CR OUT OF MEMORY return CR OK Deallocation CR Error Code CR Free Result List CR Result List x x r if r 0L 310 1 return CR NULL POINTER CR Result List cr record x r try while cr_record OL CR Result List last cr record CR Match List x cr match cr record gt match list 320 while cr match OL CR Match List x last cr match CR Match Items cr items cr match gt items while cr_items OL CR Match Items last cr items 330 Free String cr items gt subcircuit item Free String cr items gt supercircuit item cr items cr items gt next delete last cr_match cr_match gt next delete last 340 Free_String cr_record gt circuit_name Free_String cr_record gt circuit_file_loc
267. tches 1010 Check that connected_to is a subset of dv gt connections if connected_to empty for cmi dv gt connections begin cmi dv gt connections end cmi Net Vertex nv cmi second if nv assigned amp amp connected to count 1020 1 int nv gt 0 connected_to erase int nv If there is anything left in subset of dv gt connections something that dv is not return connected_to connected_to it is not a Therefore dvp is connected to dv and dvp are not equivalent empty Project Source Code 10 20 30 40 60 70 libcrdb src ohlrich circuit cc 142 D 26 libcrdb src ohlrich circuit cc include ohlrich circuit h begin code from reference implementation define randomi x x 1103515245 12345 define random2 x x 1015351425 12345 end code from reference implementation define positive x x amp INT MAX define REPORT var debug using namespace st Ohlrich Circuit counter 0 match weight Ohlrich_Circuit counter 0 match_weight Ohlrich_Circuit J JA d STRING var u u d n var Ohlrich_Circuit istream amp fd cia Spice_Interpreter fd Ohlrich_Circuit Spice_Interpreter zur Ohlrich_Circuit int Ohlrich Circuit Ver
268. tex x Vertex List int that amp t Compare_To Ohlrich Circuit amp t Match Record List amp mrl bool assume all open keynode candidate vector match_count 0 that subgraph this large graph A new match begins match_records clear this gt only find one match only_find_one_match bool only find one match Label each vertex with an initial value from randomi random2 and partition the vertices this Initial Labelling that Initial Labelling Reset Flags Reset Flags Reset Flags Reset Flags this gt Backup that gt Backup this this that that Os E gt net partition CLEAR BORDER gt dev partition CLEAR BORDER gt net partition assume all open SET BORDER gt dev partition CLEAR BORDER COPY OPEN Remove any nodes in the larger graph this that are not present in the smaller graph that Remove Diff No des this dev partition if Test Equivalence Classes that gt dev partition Can t check nets certain type in the subcircuit e g debug XYZZYuOuvfailveguiv_ONn return 0 Project Source Code There can easily be more nets of a on the border that gt dev_partition this dev partition 143 libcrdb src ohlrich circuit cc Print Partition BH thisy gt ude
269. the choice of threshold These need to be chosen carefully for a particular problem and a balance must be struck between eliminating matches that are impossible and eliminating instances of isomorphism Another advantage of RBE is that it can be implemented using a binary neural network as Turner and Austin 27 describe The website associated with their research 25 states that it has been successfully used to search a database of over 100 000 chemical structures papers on this subject are currently in preparation If an RBE approach were chosen to carry out circuit matching it would be possible to carry out a rapid search of many circuits as RBE can be applied to many possible matches at a time In addition RBE would provide a new search feature partial matching Part of one circuit could be matched to part of another which is not feasible using the algorithms discussed in this project This type of common substructure match forms the basis for the evaluation of the scheme s suitability performed by Turner and Austin 27 The probabilities involved in the RBE process could also be used to produce a score for each match that was based not only on device values but also on the degree of structural similarity This was not possible using the algorithms described in this project which could only detect exact structural matches 70 A Graph Matching Search Algorithm for an Electronic Circuit Repository 8 4 Conclusion The search
270. the stream It is terminated by the standard newline character out lt lt this lt lt An return true bool Serialisable String Read ifstream amp in string strcopy A newline terminated string is read in getline in strcopy swap strcopy return true Error handling D 32 libcrdb src spice interpreter cc include lt ctype h gt include lt stdlib h gt include spice_interpreter h P P include cr exceptions h P Project Source Code 10 20 30 40 60 70 80 libcrdb src spice interpreter cc 168 static const int IS OPEN 0x80000000 using namespace std Spice Interpreter Spice Interpreter Device Vertex List Iter cli Net Vertex Connection List Iter ncli Net Vertex List Iter nli for cli master device list begin cli master device list end cli delete cli for ncli master_connection_list begin ncli master_connection_list end ncli delete ncli for nli master net list begin nli master net list end nli delete nli void Spice Interpreter Read Spice File istream amp fd Spice subcircuits clear Spice models clear char line buffer READ LENGTH 2 bool end false Spice Node Map toplevel node map char x line list lt string gt device_definitions list lt string gt
271. thod 29 isp pod aie ds oe E ee ee E MIR a et ORC oS Dec 29 KONJE A i eee o AT Ue et PM A e a 29 bid Mrivial tests 4 x x Xo bad ek x hok Rx mom Res RUE deg Sa kodeki Re A 29 5 3 1 Numbers of devices LL 30 Loe ha bh ae JA ia e oe eS 30 5 4 How else can the search space be reduced o o o e e 32 5 5 Improving the search method 0 0002 eee ee ee ee 32 5 5 1 A part of graph se aa 32 beka A R ee 33 beech bs Ge RRO ee OR EDA SDH dy a a 34 5 5 4 Generating a part of graph 0 02 22 0000 0222 2G 34 5 5 5 A search algorithm for finding subcircuits using a part of graph 37 ge ASE ee La eee Pee a ee ee ee 37 as chars Gagan oa 38 Il Oe 38 i S 38 5 6 Improving the part of graph approach a 39 5 6 1 The data structures that are used within the algorithm 40 5 6 2 The shape of the part of graph 2e 40 Hindi Gok a Ge Grid dr ec i OS 40 LAETI 41 bf dr Serialisation s s ob koe i ee Ro A RO AR UA RR eG aa 41 os du ase SLE a A E ae ae es we DU E tpe i 41 perma A AS Aa K A na 42 asos Ass esed do Onde died 42 re 42 5 7 6 The interface for the Book Emulator a 43 6 7 7 Features that were not implemented llle 43 45 aaa a a O 45 6 1 1 The source of device values 2 a 45 E oh e G AT AIESEC A S 47 49 E ip N di ari A 49 ea 49 1 2 Automatic Teste i o xke os aaa ar A PUR OW ee 51 Tr Cr 53 al Re oe Pe MES UE EE EE 55 7 3 Evaluat
272. tion list Net Vertex List master net list string circuit name Match Record List match records functions for manipulating match records virtual void Build Match Record Spice Interpreter that private copy assign not allowed Spice Interpreter const Spice Interpreter amp assert 0 Spice_Interpreter amp operator const Spice_Interpreter amp assert 0 The following types are used for temporary data structures that are only used during loading A Spice component name typedef string Spice_Component_Name A Spice subcircuit name typedef string Spice_Subcircuit_Name A Spice model name typedef string Spice_Model_Name A SPICE external node number used for subcircuits typedef int External_Node_Number a mapping of Spice node numbers to our net vertex structures struct Spice_Node_Map Project Source Code 190 20 21 22 23 24 26 0 0 0 0 0 0 0 libcrdb include spice interpreter h std map lt Spice_Node_Number Net Vertex gt a mapping of External node numbers to Spice node numbers struct External_Net_Vertex_Map std map External Node Number Spice Node Number gt a mapping of component names to our device structures struct Spice Component Map std map Spice Component Name Device Vertex gt a mapping for type information for each SPICE model
273. to disk and read back in an object oriented fashion Although each object must be able to save and restore itself through serialisation it does not need to know how to save and restore the objects it contains It does not need to know anything whatsoever about their structure All it needs to do is tell the objects that it contains to save and restore themselves at the appropriate time The Database class serialises itself by calling the serialisation procedures in all the objects it contains in a defined order These include strings and circuit records Database does not know how these should be stored on disk that is left to the objects that contain them In C serialisation is not a feature of the language at all but it can be written without much difficulty During the development of this project the author wrote a class called Serialisable which provides the low level serialisation features that are needed The Database class inherits from Serialisable It makes use of a number of other classes that provide such things as serialisable strings integers sets and maps These classes provide the primitive objects that the database needs to hold its information and all of that information can be serialised It was discovered that only two types of primitive object need to be serialisable in order to allow anything else to be serialised as a collection of these objects Those objects are integers and strings every list map and array used in
274. tool that has been produced works effectively It is able to find circuit matches quickly and can be used to implement many different types of search There are ways in which the tool could be enhanced The use of fingerprinting techniques could speed up the existing search algorithm by allowing circuits to be eliminated more efficiently being an improvement on the methods described in Section Fingerprinting could be added without great difficulty but the time required to research it fully implement it test it and write up the entire process is probably in the region of a month By the time the rest of the circuit repository had been implemented and tested there was insufficient time left to add the fingerprinting feature The use of dummy circuits could also speed up matching but the generation of suitable circuits was found to be a difficult problem Finding a method to generate the optimal dummy circuits to be used in a particular case is a project in itself There may also be better ways to implement the tool The relaxation by elimination RBE technique 26 could not easily be added to the project It is a radically different approach to the entire problem It could bring many advantages including a speed increase there is no requirement for time wasting backtracking in RBE and a capability for partial matching but it could not simply be an extension of the tool as written RBE could be used in place of Ohlrich s algorithm in the exist
275. tural key screening process with what they refer to as finger printing To generate a molecule s fingerprint all paths through the graph of length x are found This is done for all x from 0 to the length of the longest path in the molecule Each path is added to a list so that each item in the list indicates all of the atoms and bonds that will be found along at least one path of length x Some paths in the list may be identical or equivalent they are removed For an ethanoic acid molecule Figure a the list for x 2 is given in Figure b H O HCH o o A CC O X CCO H O H COH O CO a b Figure 8 3 All the paths of length 2 in an ethanoic acid molecule a are listed in b All of the paths within a structure will also be present in any superstructure so this provides a way to screen out molecules that cannot match The Daylight tool does not compare the lists of paths directly though it applies a hashing function to them of the type used in the implementation of hash tables The hash function converts a key of any type to a hash value which is a number within a particular range The hash value is found for each item in each list and all values are logically OR ed together The resulting value can be compared in place of the list as a molecule X cannot be a superstructure of molecule Y unless all of the bits that are set to 1 in the value for Y are also set to 1 in the value for X This is a faster method than direct c
276. ual void Make Copy const Serialisable_Signature amp s P3 namespace std endif D 20 libcrdb include serialisable string h ifndef SERIALISABLE STRING H define SERIALISABLE STRING H include lt string gt include serialisable h namespace std class Serialisable_String public std string public Serialisable public Serialisable String std string Serialisable String const char s std string s Serialisable String const std string amp s std string s bool Write std ofstream amp out const bool Read std ifstream amp in virtual void Debug void const std cout lt lt this ki namespace std endif D 21 libcrdb include spice interpreter h ifndef SPICE_INTERPRETER_H define SPICE_INTERPRETER_H include lt map gt include lt list gt finclude lt string gt include lt istream gt include lt iostream gt include lt fstream gt include lt stdarg h gt include lt stdio h gt include lt assert h gt include lt ctype h gt include serialisable_signature h include serialisable_string h include constant time list h include match record h define READ LENGTH 128 namespace std class Vertex Project Source Code 30 40 60 TO 80 90 100 115 libcrdb include spice interpreter h public Vertex weight 0 finalised open is_net assigned
277. uding them The presence or absence of dummy circuits must provide a maximal amount of information to the search algorithm To this end the set of supercircuits for each dummy circuit should be as diverse as possible Because the database build must be automatic the generation of dummy circuits would also have to be automatic The generation of each dummy circuit is analogous to the document clustering problem in which each document in a corpus is automatically classified into a cluster based on its content To do this a small set of words S must be chosen from all of those in a corpus of documents such that the presence or absence of each s S in each document indicates to which cluster it belongs Generally if the size of set S is n there will be 2 clusters The words are chosen Chapter 8 Conclusions and Future Work 67 to maximise the entropy of the clusters so that as many documents are classified into each cluster as possible In the dummy circuit problem the words are the dummy circuits They must be chosen from a corpus of real circuits such that each is a subcircuit of one or more real circuits Together they must classify the real circuits into as many clusters as possible based on their presence or absence The document clustering problem is a difficult search problem it is NP complete and it is best solved by non standard computation techniques such as genetic algorithms T1 A similar technique could be use
278. ues the graph of a molecule is labelled with the types of atom and the types of bond that are present The only real difference is the scale of the problem which is far larger For example the Available Chemicals Directory 21 contains over 300 000 molecular structures some of which are made up of hundreds of atoms The Available Chemicals Directory can be searched for a particular chemical structure by tools including DiscoveryGate 22 and Daylight 20 The Daylight manual 19 describes how the tool eliminates molecules from consideration as possible matches by a screening process which is a more extensive version of the process described in Section 68 A Graph Matching Search Algorithm for an Electronic Circuit Repository Molecules are screened by what Daylight refer to as structural keys Structural keys are unusual or important features of a molecular structure The presence of a structural key in the substructure implies its presence in all of the matches so molecules can be removed from consider ation if they do not contain the correct keys This is an improved version of the screening process described in Section in which only devices and certain connection points were considered as structural keys In Daylight s search tool small substructures can also be structural keys However the types of structural key that will be used must be designed by a person Keys are not determined automatically Daylight have enhanced the struc
279. universal circuits When designing any algorithm it is wise to avoid the need to handle special cases Special cases complicate the description of the algorithm both in English and in the software itself This complication helps to hide the true function of the algorithm from the reader and increases the potential for bugs in the implementation 34 A Graph Matching Search Algorithm for an Electronic Circuit Repository A search algorithm will have to handle the circuits at both ends of the part of graph as special cases The circuits at one end have no subcircuits and the circuits at the other have no supercircuits To avoid this problem two new circuits can be introduced The empty circuit is defined as a circuit that is a subcircuit of all possible circuits including itself The universal circuit is defined as a circuit that is a supercircuit of all possible circuits including itself These circuits are analogous to the empty and universal sets Neither the empty nor the universal circuits need to have an actual circuit diagram They are just conceptual circuits that are used to simplify the search algorithm 5 5 3 Aside topological order A part of graph is a partial ordering 31 This means that some pairs of items in the graph circuits in this case are comparable the items can be put into a defined order Here it may be possible to say that circuit A is a subcircuit of circuit B But not all pairs are comparable in this wa
280. unt fclose fd printf nBuilding database n rc CR_Build amp handle if rc CR_OK printf CR Build failed 4sNn CR Get Error String rc return 1 rc CR Save Database amp handle argv 1 if rc CR OK printf CR Save Database failed when writingyto 4s Nn t s n argv 1 CR_Get_Error_String rc return 1 rc CR_Free_Handle amp handle if rc CR_OK printf CR_Free_Handle failed s n CR_Get_Error_String rc return 1 printf Database Lwasywrittenysuccessfully n return 0 D 2 apps dump_db c Project Source Code 10 20 30 40 60 93 apps search_db c dump db c This tool dumps a database to standard out The output can be run through db to davinci pl to generate a DAG in daVinci format include lt stdio h gt include lt assert h gt include lt stdlib h gt include lt string h gt include interface h int main int argc char argv CR Handle handle CR Error Code r 5 if argc 2 printf D A XX dump_db Dumpya database file to standard output n n Usage L dump_db lt database filegname gt n n return 1 rc CR_Create_Handle amp handle if rc CR_OK printf CR_Create_Handle failed y s n CR_Get_Error_String rc return 1 rc CR_Load_Database hand
281. upercircuits of B using Search and store them in set R b If AZ R then the test has failed In essence this test ensures that the search is able to find A as one of the supercircuits of every subcircuit of A It is a test of the property that subcircuit is the inverse of supercircuit a property that must always hold if the Search procedure and database are correct The test should be repeated for every circuit in the database and should also be repeated in reverse finding supercircuits of A then subcircuits of B Reflexivity Search Another property of the subcircuit and supercircuit relations is that they are reflexive A circuit is always a subcircuit of itself This can also form the basis of a test 1 Pick a circuit A that is in the database 2 Find all subcircuits of A using Search and store them in set R 3 If AZ Ri then the test has failed 4 Find all supercircuits of A using Search and store them in set Ra 5 If A Ra then the test has failed Again this test should be repeated for all circuits in the database Integration test with Ohlrich s Algorithm Another way to check the accuracy of the Search procedure s answers is to compare them with those found by Ohlrich s algorithm This test procedure ensures that the results obtained directly from using Ohlrich s algorithm and from the database are the same 1 Pick a circuit A that is in the database 2 Find all subcircuits of
282. us A B indicates that A is a subcircuit of B Each edge is labelled with a degree indicating the number of ways that A can be found in B and the topological order of each circuit appears in square brackets The label inf indicates that A can be found infinitely many times in B either because A is the empty circuit or B is the universal circuit daVinci proved to be an invaluable tool in tracing errors in the implementation Using graphs of this type it was easy to check that the Build procedure had done its job correctly The graphs are an exact representation of the contents of the database and correctness can be checked visually In addition some bugs in the program were eliminated in minutes simply because the behaviour of the program could be checked against the graph generated by daVinci If the graph of the database had not been so easy to generate the tracing of these bugs would have been very difficult Chapter 7 Evaluation 51 7 1 2 Automatic Tests Some automatic tests can be performed on the completed database These are described in this section Inverse Search Subcircuit is the inverse relation of supercircuit If A is a subcircuit of B then B is a super circuit of A Given this the Search procedure can be tested in the following way 1 Pick a circuit A that is in the database 2 Find all subcircuits of A using Search and store them in set R 3 For each circuit B in set R a Find all s
283. v_partition this gt dev partition Print Partition BH that gt dev_partition that gt dev partition Print Partition BHythis net partition this gt net partition Print Partition BHithat 7 net partition that gt net partition 80 Begin relabelling int iteration 0 while true 1 bool empty iteration debug Phase iyIteration dy nets n iteration 90 point 1 Relabeller that gt net_partition NULL Relabel_Non_Border_Vertex_Subcircuit false Relabeller this gt net_partition NULL Relabel_Non_Border_Vertex_Circuit false point 2 empty Remove_Border_Nodes that gt net_partition point 3 100 if Test_Equivalence_Classes that net partition this gt net partition debug XYZZYuOuufailveguivuiNn return 0 Remove_Diff_Nodes this gt net_partition that gt net_partition 110 point 4 if empty break debug Phase iyIteration dy devs n iteration point 5 Relabeller that gt dev_partition NULL 120 Relabel_Non_Border_Vertex_Subcircuit false Relabeller this gt dev_partition NULL Relabel_Non_Border_Vertex_Circuit false point 6 empty Remove_Border_Nodes that gt dev_partition point 7 if Test_Equivalence_Classes that gt dev partition this gt dev partition
284. ve certain features in order to produce meaningful results In this section a scoring function score X Y will be discussed The function produces a number which indicates how well X and Y are matched The features that the function should have include 1 The scoring system must be symmetric i e VX Y score X Y score Y X 2 The highest possible score comes from an exact match i e VX Y score X X gt score X Y 3 If Y is a better match for X than Y then score X Y gt score X Y The difference between the device values in Y and those in X is less significant than the difference between the device values in Y and those in X One simple scheme that might provide this would look at the proportion of devices in X that have the same value in Y and assign a score based on the number that exactly match However this is poor why should a tiny difference of 196 be reflected in a lower score It is much better to imagine the score as reflecting the significance of the difference between a value in X and a value in Y The differences that are taken into account should always be relative in order to accurately reflect their significance The difference between a 1 1k resistor and a 1 2kQ resistor is much less significant that the difference between a 100 and a 1102 resistor even though the difference is the same in both cases 1000 Using the fraction of the smaller number and the larger number gives a better rep
285. vertices around on the page B can be rearranged to look identical to A A B Figure 2 1 A and B are isomorphic graphs Any graph G is represented mathematically as a pair V E consisting of a set of vertices V and a set of edges E Each member of E is a pair of vertices v1 v3 The presence of a particular pair of vertices in E indicates that those vertices are directly connected by an edge In some graphs edges may be weighted with a cost function a weighted graph or have a particular direction a directed graph There may also be several edges linking a particular pair of vertices a multigraph in which case E is a multiset Graph B Vs Ep is isomorphic to graph A Va Ea if and only if there exists a one to one mapping f V gt V such that all vertices that are adjacent in B are adjacent in A and vice versa Formally Vice Vida evo oa EE F fie 2 1 Vv Vs 02 Vp v1 v2 Ey gt f v1 f 1 v2 Ea 5 6 A Graph Matching Search Algorithm for an Electronic Circuit Repository The graph isomorphism problem is a decision problem given two graphs A and B does a mapping f exist such that is satisfied Research into this problems began in earnest with the work of Corneil in 1970 4 Although earlier researchers such as Unger 29 had developed heuristic procedures to detect isomorphism their programs were not guaranteed to complete within a known time frame What was required was an algorithm
286. vide a few more search features e Feature 5 Search for Alternative Implementations Sometimes there is more than one way to implement a particular feature For example there are many possible designs of NAND gate some are faster than others and some have lower power consumption An annotated circuit could include references to alternative implemen tations After a search a user could be presented with a list of alternative implementations for each possible match These would help the user to understand the alternative ways of accomplishing a particular task e Feature 6 Search for Smaller or Faster Implementations Annotations could also indicate improvements that could be made to a circuit by indicating alternatives that were smaller or faster It is outside the scope of this project to suggest exactly which circuits should be present in the database or how they should be annotated It is also outside of the scope to suggest how the search results or annotations should appear to the user this is a user interface design concern Unfortunately a complete analysis of the usefulness of the search tool can only be performed once a complete set of circuits has been assembled in the database all annotated with appropriate information For the time being all that can be said is that the search tool can provide all of the features described above and it is therefore potentially useful with the correct database 7 4 Improving the Usefuln
287. xtension to the breakdown source code in which the average CPU time taken by a particular circuit comparison is measured using the times function The CPU time is used to calculate the time taken for a single comparison which is printed on the output along with the number of devices in the supercircuit involved in the comparison It is possible to plot the number of devices against the time taken on a graph Figure 7 5 was plotted from data gathered during 12 010 circuit comparisons The graph has several interesting features The majority of comparisons take less than 500 milliseconds regardless of the circuit size This is certainly a reasonable length of time for the operation to take The general trend indicates that the time taken by a search is related to its size but there is some element of chance involved Some comparisons involving large circuits take much longer than average The worst example for a circuit of size 271 takes 8 3 seconds The graph has been drawn with a logarithmic scale in order to accommodate these results One would expect Ohlrich s algorithm to operate in exponential time in the worst case since the problem that it is solving is NP complete see Section 3 2 4 Therefore it should be possible to draw a worst case bound for the time taken by the algorithm on the graph with an equation of the form y lt e in which a is a constant By rearranging the equation to the form a gt log y the minimum possible value of a
288. y rates in constant time ize size copy unctions in list required by Ohlrich Circuit 0 void push_front const _Tp amp x size copy data push front ds x void push_back const _Tp amp x size copy data push_back x 3 void pop_front void size copy data pop_front Es reference front void return data front y Project Source Code 100 110 120 10 10 libcrdb include database h 100 reference back void ds return data back iterator erase iterator p size copy return data erase p j void clear size_copy 0 data clear L3 iterator begin return data begin iterator end return data end const iterator begin const return data begin const iterator end const return data end D 7 libcrdb include cr exceptions h ifndef CR EXCEPTIONS H define CR EXCEPTIONS H namespace std extern const char extern const char extern const char extern const char database not built database already built file access error file format error RX XX X 2 y endif D 8 libcrdb include database h ifndef DATABASE_H define DATABASE H include serialisable h include serialisable circuit record h include constant time list h include match record h include queue
289. y For instance circuits 3 and 4 in Figure are not comparable neither is a subcircuit of the other If all pairs of circuits were comparable the part of graph would be a total ordering and a supercircuit subcircuit relation would exist between all pairs of circuits In a partial ordering it is often useful to refer to the topological order of an item in the ordering This is an integer number that defines the position of the item in the part of graph When an item A clearly comes before an item B in the partial ordering A s topological order number is less than B s And when two items are not comparable they have the same topological order number Algorithms for calculating the topological order can be quite simple Here is an unoptimised algorithm which will perform the task for a circuit X There is little need for an optimised algorithm during the one off job of building the database so any correct algorithm will suffice 1 Make a list of the subcircuits of X that exist Call this list L 2 If L is empty then X has topological order 0 Stop 3 If L is not empty then find the largest topological order in L and let a be set to that order This is a recursive call this algorithm is reused with X L 4 X has topological order a 1 Figure 5 4Jillustrates a part of graph in which every item has been assigned the correct topological order number by the Note that the empty and universal circuits have also been added to the f

project. The report

Contents

Download Pdf Manuals

Related Search

Related Contents