{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T11:40:01Z","timestamp":1723203601546},"reference-count":0,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"vor","delay-in-days":1461,"URL":"http:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["VLSI Design"],"published-print":{"date-parts":[[1996,1]]},"abstract":"<jats:p>In this paper, we describe <jats:italic>TOGAPS<\/jats:italic>, a Testability\u2010Oriented Genetic Algorithm for Pipeline\nSynthesis. The input to <jats:italic>TOGAPS<\/jats:italic> is an unscheduled data flow graph along with a specification\nof the desired pipeline latency. <jats:italic>TOGAPS<\/jats:italic> generates a register\u2010level description of a\ndatapath which is near\u2010optimal in terms of area, meets the latency requirement, and is highly\ntestable. Genetic search is employed to explore a 3\u2010D search space, the three dimensions\nbeing the chip area, average latency, and the testability of the datapath. Testability of a\ndesign is evaluated by counting the number of self\u2010loops in the structure graph of the data\npath. Each design is characterized by a four\u2010tuple consisting of (i) the latency and schedule\ninformation, (ii) the module allocation, (iii) operation\u2010to\u2010module binding, and (iv) value\u2010to\u2010register\nbinding. Accordingly, we maintain the population of designs in a hierarchical manner.\nThe topmost level of this hierarchy consists of the latency and schedule information,\nwhich together characterize the timing performance of the design. The middle level of the\nhierarchy consists of a number of allocations for a given latency\/schedule duplet. The lowest\nlevel of the hierarchy consists of a number of bindings for a specific latency\/schedule\/\nallocation. An initial population of designs is constructed from the given data flow graph\nusing different latency cycles whose average latency is in the specified range. Multiple\nscheduling heuristics are used to generate schedules for the DFG. For each of the resulting\nscheduled data flow graphs, we decide on an allocation of modules and registers based on a\nlower bound estimated using the schedule and latency information. The operation\u2010to\u2010module\nbinding and the value\u2010to\u2010register binding are then carried out. A fitness measure is evaluated\nfor each of the resulting data paths; this fitness measure includes one component for each of\nthe three search dimensions. Crossover and mutation operators are used to generate new\ndesigns from the current set of <jats:italic>parent<\/jats:italic> designs. The crossover operator attempts to combine\nthe properties of two designs. The mutation operators include addition and deletion of pure\ndelays before scheduling, as well as changes in the register and module allocation prior to\nbinding. The genetic algorithm applies the rule of the <jats:italic>survival of the fittest<\/jats:italic> to obtain nearoptimal\nsolution to the otherwise intractable problem of data path synthesis. We have implemented\n<jats:italic>TOGAPS<\/jats:italic> on a Sun\/SPARC 10 and studied its performance on a number of\nbenchmark examples. Results indicate that <jats:italic>TOGAPS<\/jats:italic> finds area\u2010optimal datapaths for the\nspecified latency cycle, while reducing the number of self\u2010loops in the data path.<\/jats:p>","DOI":"10.1155\/1996\/65320","type":"journal-article","created":{"date-parts":[[2007,9,18]],"date-time":"2007-09-18T12:57:06Z","timestamp":1190120226000},"page":"77-87","update-policy":"http:\/\/dx.doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["TOGAPS: A Testability Oriented Genetic Algorithm For Pipeline Synthesis"],"prefix":"10.1155","volume":"5","author":[{"given":"C. P.","family":"Ravikumar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V.","family":"Saxena","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[1996,1]]},"container-title":["VLSI Design"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/archive\/1996\/065320.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/1996\/65320","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T11:24:26Z","timestamp":1723202666000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/1996\/65320"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,1]]},"references-count":0,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1996,1]]}},"alternative-id":["10.1155\/1996\/65320"],"URL":"https:\/\/doi.org\/10.1155\/1996\/65320","archive":["Portico"],"relation":{},"ISSN":["1065-514X","1563-5171"],"issn-type":[{"type":"print","value":"1065-514X"},{"type":"electronic","value":"1563-5171"}],"subject":[],"published":{"date-parts":[[1996,1]]},"assertion":[{"value":"1996-01-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}