Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

The shortest path real-time searching algorithm of interactive domain instrument

A shortest-path, real-time search technology, applied in computing, special data processing applications, instruments, etc., can solve the problems of unrealistic frequent transformation of the full layout, inability to support adjacent search, and inability to meet real-time operation and other problems

Inactive Publication Date: 2008-05-07
北京华大九天科技股份有限公司
View PDF0 Cites 16 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, for interactive routing, this model has a big problem, because the layout data changes very frequently during interactive routing, and the entire layout needs to be converted every time, which takes a lot of time and cannot meet the requirements of real-time operation, especially For the index system that divides the layout according to the shape and position of the graph, such as quad tree, it cannot support direct adjacent search, and this kind of frequent conversion of the whole layout is even more unrealistic.

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • The shortest path real-time searching algorithm of interactive domain instrument
  • The shortest path real-time searching algorithm of interactive domain instrument
  • The shortest path real-time searching algorithm of interactive domain instrument

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0069] The whole system is divided into two parts:

[0070] Expand part (actual route part, perform search on TilePlane and directly interact with TilePlane). Module relations such as Figure 10 The specific implementation is shown in the figure.

[0071] Provide the control part of the route process, for example, search queue control, cost estimation equation; and conversion from TilePath linked list to path. Focus on the algorithm implementation of the router, not including the actual operation of the layout data; each step in the router is realized by converting to the basic expand operation of the extractor part.

[0072] Extract part (actually handle the conversion from quad-tree to the required tile-plane, convert the obstacles on the layout into a positive coordinate system, and mark out the part covered by the obstacle blocks, and distinguish the wiring area from the blocked area).

[0073] Responsible for extracting and processing the graphics in the layout, and re...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention provides a real-time shortest path search algorithm in an interactive layout tool, belonging to the technical field of the integrated circuit layout design automation, which in particular relates to an interactive layout automatic routing algorithm which can search the shortest path between designated points or units on a published picture in real time. The invention adopts a non-grid routing model with level block management, is not required to pre-extract the layout, reduces the expense for model conversion at the same time of improving the routing flexibility, and improves the path search speed by using buffered data, thereby meeting the requirement in the real-time routing in a layout editor.

Description

technical field [0001] The invention belongs to the technical field of integrated circuit layout design automation, and specifically relates to an interactive layout automatic wiring algorithm, which can search for the shortest path between designated points or units on a published diagram in real time. Background technique [0002] Automatic routing is an important technology in the field of IC layout design automation. With the continuous increase of circuit design scale and the improvement of manufacturing process precision, the work of layout and wiring becomes more and more heavy, especially in analog circuit design. Automatic routing technology can greatly reduce the workload of layout designers and improve work efficiency, while also ensuring the correctness and rationality of routing results. [0003] The automatic wiring model has undergone the transformation from the initial grid-based model (grid based) to the gridless model (gridless based), and the gridless mod...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
IPC IPC(8): G06F17/50
Inventor 苏毅杜浩斌
Owner 北京华大九天科技股份有限公司
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com