CN107491598A - Large-scale microfluidic biochip rapid wiring method and equipment - Google Patents

Abstract

The embodiment of the invention provides a method and equipment for quickly wiring a large-scale microfluidic biochip. The method comprises the following steps: reading in the connection end position information, the wiring design rule and the chip size of the biochip to be wired; dividing a region to be wired by using a divide-and-conquer strategy according to the size of a chip to obtain a plurality of wiring subregions; obtaining a wiring starting point of a wiring area to be wired by a rule-based wiring method or a semi-rule A-search algorithm in a sub-area to be wired; and wiring the wiring sub-area which is not subjected to wiring by using coordinate transformation. The device is used for executing the method, the embodiment of the invention divides the area to be wired by a divide-and-conquer strategy, and routes the connection starting point in the area to be wired by utilizing a rule-based wiring method or a semi-rule A-x search algorithm for one divided sub-area to be wired, and then routes the wiring sub-area which is not wired by utilizing coordinate transformation, thereby improving the wiring efficiency.

Description

Large-scale microfluidic biochip rapid wiring method and equipment

technical field

The embodiments of the present invention relate to the technical field of microfluidic biochip design automation, in particular to a method and equipment for rapid wiring of large-scale microfluidic biochips.

Background technique

Microfluidic biochip, also known as lab-on-a-chip, refers to the integration of basic operating units such as sample preparation, reaction, separation, and detection in biological, chemical, and medical analysis processes into a micro-nano-scale chip, forming a network of micro-channels , a technology that runs through the entire system with a controllable fluid and automatically completes the entire analysis process. Microfluidic biochip is the inevitable product of miniaturization, which can effectively reduce the amount of reagents, improve sensitivity, and bring huge economic benefits. Microfluidic biochips will be widely used in many fields such as food safety, ecological environment monitoring and protection, and disease diagnosis, and are the mainstream technology of next-generation analysis products. Compared with traditional experimental equipment, microfluidic biochips have many advantages.

First of all, considering the conditions affecting the chemical reaction rate, the small and portable lab-on-a-chip can more easily solve the problem of contact area control of reactants in the design stage, solve the problem of temperature control in the test stage, greatly shorten the reaction time of samples, and improve test efficiency. .

Second, consider the cost of testing. From the perspective of the cost of test equipment, most of the materials for making microfluidic chips are inexpensive single-crystal silicon wafers, quartz, glass and organic polymers. As long as the cost of chips is consumed during the design stage and research on the manufacturing process, After it is officially put into use, each chip will save a lot of scientific research costs. From the perspective of test reagent costs, many samples and reagents used in biological, chemical, and medical tests are either expensive or scarce, and micron-level microfluidic chips can save a lot of precious samples compared with traditional test methods.

Finally, microfluidic biochips can effectively balance the imbalance of regional medical resources or scientific research resources, so that places that cannot have advanced instruments can conveniently and effectively complete the research on disease detection, prevention, and treatment options, making it easier for those with limited funds The laboratory can conduct complex and expensive experiments, and even enables ordinary families to have more mature and effective disease control methods and improve the quality of life.

At present, the design of microfluidic biochips is mainly designed by hand, using software such as AutoCAD or even Photoshop, and trained designers manually draw the connections on the chip through software. Such a design method requires a lot of time consumption, and generally takes weeks or even months to complete. For microfluidic biochips used for drug delivery, although it can be modeled as a minimum-cost network flow problem and solved by computer programs, due to its huge scale, the solution time takes dozens of hours, which is still unacceptable. Therefore, how to improve the efficiency of automatic wiring of large-scale microfluidic biochips is an urgent problem to be solved.

Contents of the invention

In view of the problems existing in the prior art, the embodiments of the present invention provide a large-scale microfluidic biochip wiring method and equipment.

On the one hand, an embodiment of the present invention provides a method for rapid wiring of a large-scale microfluidic biochip, including:

Read in the information to be wired of the microfluidic biochip to be wired, the information to be wired includes the position information of the wiring endpoints, the wiring design rules and the chip size, and the wiring design rules include a rule-based wiring method or a semi-rule-based A * Algorithmic wiring method;

According to the size of the chip, the area to be wired is divided by using a divide-and-conquer strategy to obtain multiple wiring sub-areas;

Obtaining one of the wiring sub-areas as the sub-area to be routed, and using a rule-based routing method or a semi-regular A* search algorithm to route the starting point of the wiring in the area to be routed;

Routing is performed on the wiring sub-area that has not yet been wired according to the wiring-to-be-wiring sub-area that has been wired.

On the other hand, an embodiment of the present invention provides an electronic device, including: a processor, a memory, and a bus, wherein,

The processor and the memory communicate with each other through the bus;

The memory stores program instructions that can be executed by the processor, and the processor can execute the above method steps by calling the program instructions.

In yet another aspect, an embodiment of the present invention provides a non-transitory computer-readable storage medium, including:

The non-transitory computer-readable storage medium stores computer instructions, and the computer instructions cause the computer to execute the above-mentioned method steps.

The embodiment of the present invention provides a large-scale microfluidic biochip rapid wiring method and equipment, which divides the area to be wired by a divide-and-conquer strategy, and uses a rule-based wiring method or semi-regular A* for a sub-area to be wired. The search algorithm is used to route the starting point of the line in the sub-area to be routed, and then use the coordinate transformation to implement the route to the sub-area that has not been routed, thereby improving the efficiency of the route.

Description of drawings

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are For some embodiments of the present invention, those skilled in the art can also obtain other drawings based on these drawings without creative work.

Fig. 1 is a schematic flow chart of a rapid wiring method for a large-scale microfluidic biochip provided by an embodiment of the present invention;

2 is a schematic diagram of a coordinate transformation method provided by an embodiment of the present invention;

FIG. 3 is a schematic diagram of a rule-based wiring method provided by an embodiment of the present invention;

FIG. 4 is a schematic diagram of wiring of an A* search algorithm provided by an embodiment of the present invention;

FIG. 5 is a schematic diagram of the wiring flow of the A* search algorithm provided by the embodiment of the present invention;

FIG. 6 is a schematic diagram of wiring using the A* search algorithm provided by another embodiment of the present invention;

FIG. 7 is a schematic diagram of a physical structure of an electronic device provided by an embodiment of the present invention.

detailed description

In order to make the purpose, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the drawings in the embodiments of the present invention. Obviously, the described embodiments It is a part of embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without creative efforts fall within the protection scope of the present invention.

Fig. 1 is a schematic flow chart of a large-scale microfluidic biochip rapid wiring method provided by an embodiment of the present invention. As shown in Fig. 1, the method includes:

Step 101: Read in the information to be wired of the microfluidic biochip in the area to be wired. The information to be wired includes the location information of the starting point of the wiring, the wiring design rules and the chip size. The wiring design rules include rule-based wiring methods or based on The semi-regular A* algorithm wiring method; specifically, the information to be wired of the microfluidic biochip to be wired is obtained, wherein the information to be wired includes the location information of the starting point of the wiring, the wiring design rules and the chip size. It should be noted that the connection The line starting point information refers to the connection starting point information and the connection end information on the area to be wired. The so-called starting point of the line is the internal starting point in the area to be wired, and the end point of the line is the control pin on the edge of the area to be wired. The purpose is to realize the fast connection of the start point and the end point of the connection. The connection start information may include the number of connection start points in the area to be routed and the positions of each line start point; the connection end information may include the number of control pins in the area to be routed and the positions of each control pin. Routing design rules include rule-based routing methods or semi-rule-based A* algorithm routing methods. It can be understood that the information to be routed may also include other information, such as the distance between the starting points of two connection lines, etc., which is not specifically limited in this embodiment of the present invention.

Step 102: According to the size of the chip, divide the area to be wired by using a divide-and-conquer strategy to obtain multiple wiring sub-areas;

Specifically, after obtaining the size of the area to be routed, the area to be routed is divided according to the size of the area to be routed, and the division adopts a divide-and-conquer strategy, which is to divide large-scale problems into Multiple small-scale sub-problems, multiple sub-problems are independent of each other and have the same form as the original large-scale problem, through solving the small-scale sub-problems, and then combining the solutions of each sub-problem to obtain the solution of the large-scale problem. For example: the width of the area to be wired is w in the horizontal direction, and the height in the vertical direction is h. The area to be wired can be divided into 4 wiring sub-areas by diagonal lines. The specific formula for the division is:

It should be noted that the area to be wired may be divided into multiple wiring sub-areas according to actual conditions, which is not specifically limited in this embodiment of the present invention.

Step 103: Obtain one sub-area to be routed as the sub-area to be routed, and use a rule-based routing method or a semi-regular A* search algorithm to route the starting point of the wiring in the sub-area to be routed;

Specifically, a wiring sub-area obtained after division is taken as the sub-area to be routed, and the wiring starting point of the sub-area to be routed can be routed through a rule-based routing method or a semi-rule-based A* search algorithm , wherein, the rule-based routing method is to determine the routing rules in advance according to the position information of the current connection starting point in the sub-area to be routed. After the routing rules are determined, the routing can be completed according to the routing rules. The semi-rule-based A* search algorithm is to determine the wiring order of the starting point of the connection in the wiring area in advance, and use the A* search algorithm to route according to the wiring order. An effective method, the optimal path of the current connection starting point in the routing process can be realized through the A* search algorithm.

Step 104: Routing the wiring sub-area that has not been wired according to the wiring-to-be-routing sub-area that has been routed using coordinate transformation.

Specifically, after the wiring is completed in the sub-areas to be wired, coordinate transformation is used to perform wiring on the unfinished wiring sub-areas in the area to be wired. Assuming that the area to be wired is divided into 8 wiring sub-areas, Figure 2 is a schematic diagram of the coordinate transformation method provided by the embodiment of the present invention, as shown in Figure 2, the wiring sub-area labeled 1 is obtained as the area to be wired, and the number 1 After the wiring sub-area is completed, the coordinate transformation is carried out through the formula (1) to complete the wiring of the No. 2 wiring sub-area; the wiring of the No. 3 wiring sub-area is completed through the formula (2); the No. 4 wiring is completed through the formula (3) Wiring in the sub-area; completing the wiring in the No. 5 wiring sub-area by formula (4); completing the wiring in the No. 6 wiring sub-area by formula (5); completing the wiring in the No. 7 wiring sub-area by formula (6); completing the wiring in the No. 7 wiring sub-area by formula ( 7) Complete the wiring of the No. 8 wiring sub-area, and the coordinate transformation formula is as follows:

The wiring of the entire area to be wired can be realized through the above-mentioned coordinate transformation. It should be noted that when selecting the area to be wired from the wiring sub-areas, one can be selected, or two or more can be selected. The implementation of the present invention The example does not specifically limit this.

In the embodiment of the present invention, the area to be wired is divided by a divide-and-conquer strategy, and a rule-based routing method or a semi-rule A* search algorithm is used to route the starting points of the wiring in the area to be wired, and then coordinate transformation is used to realize the wiring Routing is performed on the routing sub-regions that have not been routed, thereby improving the efficiency of routing.

On the basis of the above-mentioned embodiments, the division of sub-regions to be wired by using the divide-and-conquer strategy includes:

Divide the area to be wired into 4 wiring sub-areas by using a horizontal central axis and a vertical central axis, or divide the area to be wired into 8 wiring sub-areas by using a horizontal central axis, a vertical central axis and a diagonal line subregion.

Specifically, using the regular characteristics of microfluidic biochips, that is, microfluidic biochips are generally rectangular or square, and the culture chambers in microfluidic biochips are evenly distributed, wherein each culture chamber is a connection starting point, so the area to be wired can be divided into 4 equally divided wiring sub-areas through the horizontal central axis and the vertical central axis. Alternatively, the area to be wired can be divided into 8 equally divided wiring sub-areas by using the horizontal axis, the vertical axis and the diagonal. The specific method of division has been described in the above embodiments, and will not be repeated here.

On the basis of the above embodiments, the routing of the starting points of the wiring in the sub-area to be wired using a rule-based routing method includes:

The routing rule of the starting point of the current connection is calculated according to the preset rule, and the routing is performed on the starting point of the current connection in the sub-area to be routed according to the routing rule.

Specifically, the current connection start point is obtained from all the connection start points included in the sub-area to be routed. During the routing process, one connection start point and one connection start point are required for wiring, and the current connection start point is the current connection point that needs to be routed. line starting point. According to the position information of the starting point of the current connection and the information of the area to be routed, the preset rules are used to calculate the routing rules of the starting point of the current connection, and the starting point of the current connection is routed according to the routing rules. The routing rule is to specify the starting point of the current connection Routing path, so that the current node is routed along the planned routing path.

The embodiment of the present invention calculates and obtains the routing rules of the current connection starting point through preset rules, and performs routing to the current connection starting point according to the routing rules, thereby realizing automatic routing of the area to be routed.

On the basis of the above embodiments, the calculation according to the preset rules to obtain the wiring rules of the starting point of the current connection includes:

According to the formula Calculate and obtain the wiring rule of the starting point of the current connection;

Wherein, w is the width of the area to be wired in the x-axis direction, h is the height of the area to be wired in the y-axis direction, n is the number of repetitions required in the wiring process, and m is the required number of times in the wiring process Move step size, x _w is the number of points to be routed corresponding to the row where the starting point of the current connection is located, x _h is the number of points to be routed corresponding to the column where the starting point of the current connection is located, and i is the number of points to be routed corresponding to the column where the starting point of the current connection is located, and i is the current connection The number of rows corresponding to the starting point, y is the ordinate value corresponding to the starting point of the current connection during the wiring process, pitch _w is the distance between the starting point of the connecting line in the abscissa direction, pitch _h is the starting point of the connecting line on the y-axis The spacing in the direction.

Specifically, the formula (8) is some parameter calculation formulas used in the preset rules, where the formula (8) is as follows:

Establish a Cartesian coordinate system according to the area to be routed, w in formula (8) is the width of the area to be routed in the x-axis direction, h is the height of the area to be routed in the y-axis direction, and n is the starting point of the current connection during the routing process The number of repetitions is required, m is the moving step size required in the wiring process of the current connection start point, x _w is the number of points to be routed corresponding to the row where the current connection start point is located, x _h is the number of points to be routed corresponding to the column where the current connection start point is located The number of routing points, i is the number of rows corresponding to the starting point of the current connection, y is the ordinate value corresponding to the starting point of the current connection during the routing process, pitch _w is the distance between the starting point of the connecting line in the direction of the abscissa, and pitch _h is the distance between the starting point of the connecting line The distance between the starting points of the lines in the y-axis direction. If the starting points of the lines are evenly distributed on the sub-areas to be routed, then pitch _h = pitch _w . It should be noted that the pitch _w calculated by the above formula is the minimum spacing of the starting point of the connection in the sub-area to be routed, and the final method for determining the spacing of the starting point of the connection is to obtain the maximum spacing of the starting point of the connection in the sub-area to be routed , according to the minimum distance and the maximum distance, use the dichotomy method to obtain the final distance between the starting points of the connection. The calculation method of pitch _w is similar to the above, and will not be repeated here.

In the embodiment of the present invention, some parameters in the wiring rules are calculated by formulas, and the wiring rules of the starting point of the current connection are obtained according to these parameters, so as to realize the automatic wiring of the sub-area to be wired.

On the basis of the foregoing embodiments, the wiring rules include:

S501. Obtain the coordinates of the starting point of the current connection, and determine a first wiring direction according to the coordinates of the starting point of the current connection and the side where the ending point of the connection is located, and the wiring direction is parallel to the x-axis or parallel to the y-axis;

Specifically, the coordinates of the starting point of the current connection in the sub-region to be routed are obtained, and the first routing direction is determined according to the coordinates of the starting point of the current connection and the side where the end point of the connection is located, as shown in Figure 2. They are all on the right side of the side where the end point of the line is located. Therefore, the first wiring direction is left, and it can also be the negative direction of the x-axis, as shown in the No. 2 wiring sub-area in Figure 2. All the starting points of the line are at the end point of the line. Therefore, the first wiring direction is down, which may also be the negative direction of the y-axis.

S502. Move once along the first wiring direction;

Specifically, starting from the starting point of the current connection and moving once along the first routing direction, it should be noted that the distance moved once along the first routing direction is the distance between the starting point of the current connection in the first routing direction, Taking the No. 2 wiring sub-area in FIG. 2 as an example, starting from the starting point of the current connection, move downward once, and the moving distance is pitch _h .

S503. Alternately move n times along the second wiring direction perpendicular to the wiring direction and the first wiring direction;

Specifically, after moving once along the first wiring direction, then alternately move n times along the second wiring direction and the first wiring direction, that is, first move once along the second wiring direction, and then move along the first wiring direction Moving once is repeated n times in total, wherein the second routing direction is perpendicular to the first routing direction, and the moving distance in the second routing direction is the distance between the starting point of the current connection in the second routing direction. Still taking the No. 2 wiring sub-area in Figure 2 as an example, first move the pitch _w distance to the left or right, and then move the pitch _h distance downward. It should be noted that whether the second wiring direction is to the left or to the right may be determined according to actual conditions.

S504. Move along the second wiring direction, and the moving distance is m;

Specifically, after executing S403, move along the second direction, and the moving distance is m, and the specific value of m can be calculated by m=i−y+2*pitch _h .

S505. Move along the first wiring direction until the end point of the connection is reached;

Specifically, continue to move along the first routing direction, and when the routing reaches the end point of the connection, the routing to the starting point of the current connection is completed.

In the embodiment of the present invention, a rule-based routing method is used to route the starting point of the connection in the area to be routed, and the algorithm can complete the routing relatively quickly and improve the efficiency of the routing.

On the basis of the foregoing embodiments, the wiring rules include:

S601. Acquire the coordinates of the starting point of the current connection, and determine a first wiring direction according to the coordinates of the starting point of the current connection and the side where the ending point of the connection is located, and the wiring direction is parallel to the x-axis or parallel to the y-axis;

Specifically, the coordinates of the starting point of the current connection in the region to be routed are obtained, and the first routing direction is determined according to the coordinates of the starting point of the current connection and the side where the end point of the connection is located, as shown in Figure 2. On the right side of the side where the end point of the connection is located, therefore, the first wiring direction is left, that is, the negative direction of the x-axis, as shown in the No. 2 wiring sub-area in Figure 2, all the starting points of the connection are above the end point of the connection, Therefore, the first wiring direction is downward, that is, the negative direction of the y-axis.

S602. The moving distance along the first wiring direction is P-(aa _i ), where P is the distance between the starting point of the current wiring in the first wiring direction, and a is the distance between the starting point of the current wiring in the first wiring direction. The number of connection starting points that need to be wired corresponding to the first wiring direction, a _i is the serial number corresponding to the current connection starting point in the first wiring direction;

Specifically, starting from the starting point of the current connection, move along the first wiring direction, wherein the moving distance is P-(aa _i ), taking the starting point of a connection in the No. 2 wiring sub-area in Figure 2 as an example, if There are a total of 6 connection start points in the column where the current connection start point is located, and the current connection start point is located in the fourth column, that is, the serial number corresponding to the current connection start point in this column is 4, which is formed from the connection end point The number of sides starts, and the distance between the starting points of the two lines in the vertical direction is P=4, so the distance that the starting points of the current line need to move is 4-(6-4)=2.

S603. Alternately move n times along the second wiring direction perpendicular to the wiring direction and the first wiring direction, and if it is determined that an obstacle is encountered while moving along the second wiring direction, move along the moving in the first routing direction until the obstacle is avoided;

Specifically, after moving once along the first wiring direction, then alternately move n times along the second wiring direction and the first wiring direction, that is, first move once along the second wiring direction, and then move along the first wiring direction Moving once is repeated n times in total, wherein the second routing direction is perpendicular to the first routing direction, and the moving distance in the second routing direction is the distance between the starting point of the current connection in the second routing direction. If you encounter an obstacle while wiring along the second wiring direction, then move along the first wiring direction until you avoid the obstacle, and then follow the second wiring direction after avoiding the obstacle. Therefore, before encountering an obstacle , the sum of the moving distance in the second routing direction and the moving distance in the second routing direction after avoiding obstacles should be equal to the distance between the starting point of the current connection in the second routing direction. For example, if the distance to move in the second routing direction is 5, and an obstacle is encountered when the moving distance is 2, then after avoiding the obstacle, the distance to move along the second routing direction is 3. It should be noted that the obstacle avoidance processing method in the first wiring direction is consistent with the obstacle avoidance in the second wiring direction in principle, that is, when wiring along the first wiring direction, if an obstacle is encountered, the Move in the second routing direction until the obstacle is avoided, and continue routing along the first routing direction after the obstacle is avoided. It should be noted that the second wiring direction is perpendicular to the first wiring direction, but there are two directions perpendicular to the first wiring direction, and which direction to choose can be preset according to actual conditions.

S604. Move along the second wiring direction, if it is determined that an obstacle is encountered while moving along the second wiring direction, move along the first wiring direction until the obstacle is avoided, and The distance moved along the second wiring direction is m;

Specifically, after executing S503, move along the second wiring direction, and the moving distance is m, and the specific value of m can be calculated by m=i−y+2*pitch _h . During the process of moving the wiring, if an obstacle is encountered, move along the first wiring direction until the obstacle is avoided, and then continue to move along the second wiring direction.

S605. Move along the first wiring direction until the end point of the connection is reached;

Wherein, the distance to move once along the first wiring direction is the distance between the starting point of the current connection in the first wiring direction; the distance to move once along the second wiring direction is the distance of the current connection The pitch of the starting point in the second wiring direction.

FIG. 3 is a schematic diagram of a rule-based wiring method provided by an embodiment of the present invention. As shown in FIG. 3 , the origin indicates the starting point of the current connection, the black solid line is the wiring situation of the rule-based wiring method, and the black squares are obstacles.

The embodiment of the present invention adds an obstacle avoidance algorithm on the basis of the rule-based wiring method, so that if an obstacle is encountered during the wiring process, the wiring can be bypassed. , and improve wiring efficiency.

On the basis of the above embodiments, the routing of the starting point of the connection in the region to be routed using the semi-rule-based A* search algorithm includes:

Obtaining all connection start points in the to-be-wired sub-area, and storing the first numbers corresponding to the connection start points in the first array;

According to the preset rules, the starting point of the connection line corresponding to the first number in the middle position in the first array is used as the starting point of the middle connection line, starting from the starting point of the middle connection line, sequentially pairing the starting point of the middle connection line adjacent to the starting point of the middle connection line and The starting point of the connection that has not been routed is routed using the A* search algorithm.

Specifically, to obtain all the connection start points in the sub-area to be routed, the connection start points can be numbered in advance according to the preset rules, specifically, all the connection start points can be projected onto the edge formed by the connection end points , and then number the start points of the lines from left to right, or from top to bottom. It should be noted that if there are two or more start points of the lines projected onto a point, then the distance from the end points of the lines is first The starting points of the outlying lines are numbered. Store the first number of the starting point of the connection into the first array in order of size. It can be understood that the end points of the connection can also be numbered sequentially, and the second number corresponding to the end point of the connection can be stored in the second array.

First, get the first number in the middle from the first array, and use the starting point of the line corresponding to the first number in the middle as the starting point of the middle line. Similarly, get the second number in the middle from the second array , use the end point of the connection line corresponding to the second most middle number as the end point of the middle connection line, and use the A* search algorithm to route the start point and end point of the middle connection line. For example: the first array is [0, 1, 2, 3, 4, 5, 6], at this time, the starting point of the line corresponding to the first number 3 should be selected as the starting point of the middle line, and the first array is [ 0, 1, 2, 3, 4, 5], then, there are two in the middle of the first array, which are 2 and 3 respectively. In this case, the first number can be preset to be smaller or smaller The larger one is used as the starting point of the middle connection. Then extend the wiring from the starting point of the middle connection line to both sides in turn, that is, sequentially select the first number corresponding to the starting point of the middle connection line in the first array, and perform wiring on the connection starting point corresponding to the first number adjacent to the starting point of the middle connection line, and similarly The end point of the line corresponding to the second number adjacent to the end point of the line is selected from the array, and the A* search algorithm is used again for wiring, and so on. Fig. 4 is a schematic diagram of wiring of an A* search algorithm provided by an embodiment of the present invention. As shown in Fig. 4, the area to be wired is first divided into 4 parts by diagonal lines, and the lowermost triangular area is wired, and the triangular area is first obtained In the area, the starting point of the connection corresponding to the first number in the middle of the first array is routed, that is, the uppermost point in Figure 4, and then the points adjacent to the uppermost point are routed on both sides, as shown in Fig. 4 is a schematic diagram of the starting point of the three connections that have completed the wiring.

In the embodiment of the present invention, by specifying the order of wiring and using the A* search algorithm to perform wiring according to the wiring order, the wiring can be quickly completed in the area to be wired.

On the basis of the above embodiments, FIG. 5 is a schematic diagram of the wiring flow of the A* search algorithm provided by the embodiment of the present invention. As shown in FIG. 5, the wiring using the A* search algorithm includes:

Step 701, define the extension cost of the connection starting point; calculate the extension cost of the connection starting point through the evaluation function of the A* algorithm.

Step 702: Create a linked list of nodes to be expanded, and save all visited but unexpanded nodes according to the order of expansion cost from small to large. The node is a searched but unexpanded grid point in the sub-area to be routed ; Use the evaluation function to calculate the expansion cost corresponding to each node to be expanded. It should be noted that the embodiment of the present invention performs wiring under the condition of a grid.

Step 703, judging whether there is a node to be expanded in the node list to be expanded, if the judgment result is yes, then execute step 704, otherwise the search ends and output search failure;

Step 704, read the node with the smallest expansion cost in the linked list of nodes to be expanded, record it as the current node to be expanded, and judge whether the current node to be expanded is the end point of the connection, if the judgment result is yes, the search ends, and the output is successful, Otherwise execute step 705;

Step 705, traversing the expansion direction allowed by the current node to be expanded, finding out all nodes in the allowed expansion direction, and inserting them into the adjacent point list;

Step 706, traversing the list of adjacent points, and generating a plurality of new expansion nodes for the current node to be expanded;

Step 707, calculate the expansion cost of the new expansion node, and insert it into the appropriate position of the node list to be expanded according to the calculated expansion cost;

Step 708, repeating steps 704 to 707 until the end of the search, obtaining the target wiring path from the start point of the connection to the end point of the connection;

Step 709, according to the wiring path, obtain the node to be expanded with the Manhattan distance of 1 in the wiring path, and store it in the list to be detected, if it is determined that the node to be expanded in the list to be detected has passed If there is a corresponding routing path at the starting point of any uncompleted routing, the target routing path is output. If the node to be expanded in the list to be detected does not enable any uncompleted wiring starting point to find a routing path, it means that the target routing path is illegal, that is, the current starting point of the connecting line cannot be routed. From the first array Obtain the starting point of the next column adjacent to the starting point of the current connecting line and perform wiring.

FIG. 6 is a schematic diagram of wiring using the A* search algorithm provided by another embodiment of the present invention. As shown in FIG. 6 , the wiring of the lowest wiring sub-area after the area to be wired is divided is completed through the A* search algorithm.

The embodiment of the present invention uses the A* search algorithm to route the connection starting point of the area to be routed, and completes the wiring of the area to be routed by using coordinate transformation to complete the wiring of other wiring sub-areas in the area to be routed, thereby improving the efficiency of routing .

On the basis of the above-mentioned embodiments, the extended cost of defining the starting point of the connection includes:

The extended cost of the starting point of the connection is defined by an evaluation function, wherein the evaluation function is:

f(n)=g(n)+h(n);

Wherein, f(n) is the evaluation function from the starting point of the connection to the end point of the connection via the node n, g(n) is the distance from the starting point of the connection to the routed path of the current node, h(n ) is the Manhattan distance from the current node to the endpoint of the connection.

Specifically, the expansion cost of the starting point of the connection can be calculated by the formula f(n)=g(n)+h(n), where g(n) is the distance from the starting point of the connection to the routed path of the current node, h (n) is the Manhattan distance from the current node to the endpoint of the connection. It should be noted that the value of the node to be expanded can also be evaluated through the above formula.

In the embodiment of the present invention, the area to be wired is divided by a divide-and-conquer strategy, and a semi-regular A* search algorithm is used to route the starting point of the line in the sub-area to be wired, and then coordinate transformation is used to realize the unfinished wiring. The wiring sub-region is used for wiring, thereby improving the efficiency of wiring.

FIG. 7 is a schematic diagram of the physical structure of an electronic device provided by an embodiment of the present invention. As shown in FIG. 7, the electronic device includes: a processor (processor) 801, a memory (memory) 802, and a bus 803; wherein,

The processor 801 and the memory 802 complete mutual communication through the bus 803;

The processor 801 is used to call the program instructions in the memory 802 to execute the methods provided by the above-mentioned method embodiments, for example, including: reading in the information to be wired of the microfluidic biochip to be wired, and the wiring to be wired The information includes the position information of the starting point of the connection, the wiring design rule and the chip size, and the wiring design rule includes a rule-based wiring method or a semi-rule-based A* search algorithm wiring method; according to the chip size, the divide-and-conquer strategy is used to The wiring area is divided to obtain a plurality of wiring sub-areas; one of the wiring sub-areas is obtained as a sub-area to be routed, and a rule-based routing method or a semi-regular A* search algorithm is used to search for the wiring in the sub-area to be routed Routing is performed at the starting point; according to the sub-areas to be routed that have been routed, the routing sub-areas that have not been routed are routed by coordinate transformation.

This embodiment discloses a computer program product, the computer program product includes a computer program stored on a non-transitory computer-readable storage medium, the computer program includes program instructions, and when the program instructions are executed by the computer, the computer The method provided by each of the above method embodiments can be executed, for example, including: reading in the information to be wired of the microfluidic biochip to be wired, the information to be wired includes the position information of the starting point of the wiring, wiring design rules and chip size, the The wiring design rules include a rule-based wiring method or a semi-rule-based A* search algorithm wiring method; according to the chip size, use a divide-and-conquer strategy to divide the area to be wired to obtain multiple wiring sub-areas; obtain one of the wiring The sub-region is used as a sub-region to be routed, and the starting point of the connection in the sub-region to be routed is routed using a rule-based routing method or a semi-regular A* search algorithm; according to the sub-region to be routed that has completed routing, use Coordinate transformation performs routing on the routing sub-area that has not been routed.

This embodiment provides a non-transitory computer-readable storage medium, the non-transitory computer-readable storage medium stores computer instructions, and the computer instructions cause the computer to execute the methods provided in the above method embodiments, for example, including : Read in the information to be wired of the microfluidic biochip to be wired, the information to be wired includes the position information of the starting point of the wiring, the wiring design rules and the chip size, and the wiring design rules include a rule-based wiring method or a semi-rule-based A* search algorithm wiring method; according to the size of the chip, divide the area to be wired by using a divide-and-conquer strategy to obtain multiple wiring sub-areas; obtain one of the wiring sub-areas as the sub-area to be wired, and use a rule-based wiring method Or a semi-regular A* search algorithm is used to route the starting point of the wiring in the sub-area to be routed; according to the sub-area to be routed that has been routed, use coordinate transformation to route the wiring sub-area that has not been routed .

Those of ordinary skill in the art can understand that all or part of the steps for realizing the above-mentioned method embodiments can be completed by hardware related to program instructions, and the aforementioned program can be stored in a computer-readable storage medium. When the program is executed, the It includes the steps of the above method embodiments; and the aforementioned storage medium includes: ROM, RAM, magnetic disk or optical disk and other various media that can store program codes.

The devices and other embodiments described above are only illustrative, and the units described as separate components may or may not be physically separated, and the components shown as units may or may not be physical units, that is, they may Located in one place, or can be distributed to multiple network elements. Part or all of the modules can be selected according to actual needs to achieve the purpose of the solution of this embodiment. It can be understood and implemented by those skilled in the art without any creative efforts.

Through the above description of the implementations, those skilled in the art can clearly understand that each implementation can be implemented by means of software plus a necessary general hardware platform, and of course also by hardware. Based on this understanding, the essence of the above technical solution or the part that contributes to the prior art can be embodied in the form of software products, and the computer software products can be stored in computer-readable storage media, such as ROM/RAM, magnetic discs, optical discs, etc., including several instructions to make a computer device (which may be a personal computer, server, or network device, etc.) execute the methods described in various embodiments or some parts of the embodiments.

Finally, it should be noted that: the above embodiments are only used to illustrate the technical solutions of the present invention, rather than to limit them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that: it can still be Modifications are made to the technical solutions described in the foregoing embodiments, or equivalent replacements are made to some of the technical features; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the spirit and scope of the technical solutions of the various embodiments of the present invention.

Claims (11)

1. A large-scale microfluidic biochip rapid wiring method is characterized by comprising the following steps:

reading information to be wired of the microfluidic biochip to be wired, wherein the information to be wired comprises wiring starting point position information, wiring design rules and chip sizes, and the wiring design rules comprise a rule-based wiring method or a semi-rule-based A-search algorithm wiring method;

dividing the area to be wired by using a dividing and controlling strategy according to the size of the chip to obtain a plurality of wiring sub-areas;

obtaining one wiring subregion as a subregion to be wired, and wiring a wiring starting point in the subregion to be wired by using a rule-based wiring method or a semi-regular A-search algorithm;

and according to the to-be-wired subarea which is wired, wiring the to-be-wired subarea which is not wired by utilizing coordinate transformation.

2. The method of claim 1, wherein the dividing the sub-regions to be wired by using the divide and conquer strategy comprises:

adopt horizontal axis and perpendicular axis will treat that the wiring area divides into 4 wiring subregion, or adopt horizontal axis, perpendicular axis and diagonal will treat that the wiring area divides into 8 wiring subregion.

3. The method according to claim 1, wherein the routing the starting point of the wire in the sub-area to be routed by using a rule-based routing method comprises:

and calculating a wiring rule of the current wiring starting point according to a preset rule, and wiring the current wiring starting point in the sub-area to be wired according to the wiring rule.

4. The method according to claim 3, wherein the calculating the wiring rule of the current connection starting point according to the preset rule includes:

according to the formulaCalculating to obtain a wiring rule of the starting point of the current connecting line;

wherein w is the width of the area to be wired in the x-axis direction, h is the height of the area to be wired in the y-axis direction, n is the number of times of repetition required in the wiring process, m is the moving step length required in the wiring process, and x_wStarting point for the current connecting lineThe number of the points to be wired corresponding to the row, x_hThe number of the points to be wired corresponding to the column where the current connection starting point is located, i is the number of rows corresponding to the current connection starting point, y is a longitudinal coordinate value corresponding to the current connection starting point in the wiring process, and pitch_wFor the distance of the starting point of the connecting line in the direction of the abscissa, pitch_hThe distance between the starting points of the connecting lines in the y-axis direction.

5. The method of claim 4, wherein the routing rule comprises:

s501, obtaining the coordinates of the starting point of the current connecting line, and determining a first wiring direction according to the coordinates of the starting point of the current connecting line and the edge where the terminal point of the connecting line is located, wherein the wiring direction is parallel to an x axis or a y axis;

s502, moving once along the first wiring direction;

s503, alternately moving for n times along a second wiring direction perpendicular to the wiring direction and the first wiring direction;

s504, moving along the second wiring direction by a moving distance of m;

s505, moving along the first wiring direction until the first wiring direction reaches the wiring end point;

the distance moved once along the first wiring direction is the distance of the starting point of the current connecting line in the first wiring direction; and the distance moved once along the second wiring direction is the distance between the starting point of the current connecting line and the second wiring direction.

6. The method of claim 4, wherein the routing rule comprises:

s601, obtaining the coordinates of the starting point of the current connecting line, and determining a first wiring direction according to the coordinates of the starting point of the current connecting line and the edge where the terminal point of the connecting line is located, wherein the wiring direction is parallel to an x axis or a y axis;

s602, the moving distance along the first wiring direction is P- (a-a)_i) Wherein P isThe distance between the current connecting line starting points in the first wiring direction, a is the number of the connecting line starting points needing wiring corresponding to the current connecting line starting points in the first wiring direction, and a_iA corresponding serial number of the starting point of the current connecting line in the first wiring direction is obtained;

s603, alternately moving the substrate in a second wiring direction perpendicular to the wiring direction and the first wiring direction n times, and if it is determined that an obstacle is encountered while moving the substrate in the second wiring direction, moving the substrate in the first wiring direction until the obstacle is avoided;

s604, moving along the second wiring direction, if judging that an obstacle is encountered during moving along the second wiring direction, moving along the first wiring direction until the obstacle is avoided, wherein the moving distance along the second wiring direction is m;

s605, moving along the first wiring direction until the first wiring direction reaches the wiring end point;

the distance moved once along the first wiring direction is the distance of the starting point of the current connecting line in the first wiring direction; and the distance moved once along the second wiring direction is the distance between the starting point of the current connecting line and the second wiring direction.

7. The method according to claim 1, wherein the routing the starting point of the wire in the sub-area to be routed by using a semi-rule based a-search algorithm comprises:

acquiring all the starting points of the connecting lines in the sub-area to be wired, and storing a first number corresponding to the starting points of the connecting lines into a first array;

and taking the connecting line starting point corresponding to the first number at the middle position in the first array as an intermediate connecting line starting point according to a preset rule, and sequentially routing the connecting line starting points which are adjacent to the intermediate connecting line starting point and have no wiring by using the A-x search algorithm from the intermediate connecting line starting point.

8. The method of claim 7, wherein said routing using said A-search algorithm comprises:

step 701, defining the expansion cost of the starting point of the connecting line;

step 702, creating a linked list of nodes to be expanded, and storing all accessed nodes which are not expanded according to the sequence of expanding cost from small to large, wherein the nodes are grid points which are searched for in the sub-region to be wired and are not expanded;

step 703, judging whether a node to be expanded exists in the node chain table to be expanded, if so, executing step 704, otherwise, finishing the search and outputting a search failure;

step 704, reading the node with the minimum expansion cost in the node chain table to be expanded, recording the node as the current node to be expanded, judging whether the current node to be expanded is a connection end point, if so, ending the search, outputting the search success, otherwise, executing step 705;

step 705, traversing the extension direction allowed by the current node to be extended, finding out all nodes in the extension direction allowed, and inserting the nodes into the adjacent point list;

step 706, traversing the neighbor point list, and generating a plurality of new expansion nodes aiming at the current nodes to be expanded;

step 707, calculating the expansion cost of the new expansion node, and inserting the expansion cost into an appropriate position of the node linked list to be expanded according to the calculated expansion cost;

step 708, repeating steps 704 to 707 until the search is finished, and obtaining a target wiring path from the starting point of the connection line to the end point of the connection line;

709, obtaining a node to be expanded with a manhattan distance of 1 of the wiring path according to the wiring path, storing the node to be expanded into a list to be detected, and outputting the target wiring path if the node to be expanded in the list to be detected is judged and known to pass through and a corresponding wiring path can be obtained at any connection starting point of unfinished wiring.

9. The method of claim 7, wherein the defining the extended cost of the starting point of the connection comprises:

defining the extended cost of the starting point of the connecting line by using a valuation function, wherein the valuation function is as follows:

f(n)＝g(n)+h(n)；

wherein f (n) is an evaluation function from the connection starting point to the connection end point via the node n, g (n) is a distance from the connection starting point to a routed path of a current node, and h (n) is a Manhattan distance from the current node to the connection end point.

10. An electronic device, comprising: a processor, a memory, and a bus, wherein,

the processor and the memory are communicated with each other through the bus;

the memory stores program instructions executable by the processor, the processor invoking the program instructions to perform the method of any of claims 1-9.

11. A non-transitory computer-readable storage medium storing computer instructions that cause a computer to perform the method of any one of claims 1-9.