Browsing by Author "Hsiao, PY"

Now showing 1 - 15 of 15

An O(NlogN) algorithm for region definition using channels switchboxes and ordering assignment
(1996)
Yan, JT
;
Hsiao, PY
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
For a building block placement, the routing space can be further partitioned into channels and switchboxes. In general, the definition of switchboxes releases the cyclic channel precedence constraints and further yields a safe routing ordering process. However, switchbox routing is more difficult than channel routing. In this paper, an O(NlogN) region definition and ordering assignment (RDAOA) algorithm is proposed to minimize the number of switchboxes for the routing phase, where N is the number of vertices in a channel precedence graph. Several examples have been tested on the proposed algorithm, and the experimental results are listed and compared.
Macro-cell placement fos custom-chip design using self-organizing fuzzy technique
(1998-01-01)
Chang, RI
;
Hsiao, PY
;
資訊工程學系
;
Department of Computer Science
In this paper, a new optimization technique called SOFT (self-organizing fuzzy technique) is proposed to solve the macro-cell placement problem. In SOFT, different criteria are simultaneously accounted by a novel fuzzy gain function which models expert knowledge to control the optimization process. The presented procedure is an adaptation of Kohonen's self-organization algorithm which is well suited for implementation on massively parallel architecture for fast computing. The MCNC benchmark examples are presented to verify the performance and feasibility of SOFT. Comparisons are made with the Hopfield network, SOAP and TimberWolf MC5.6. Experiments show that the proposed method yields an average of 17% improvement in total wire length compared with previous methods. Large size problems with 225 and 1024 arbitrarily-sized macrocells are also presented.
Macro-cell placement fos custom-chip design using self-organizing fuzzy technique
(1998-01-01)
Chang, RI
;
Hsiao, PY
;
資訊工程學系
;
Department of Computer Science
In this paper, a new optimization technique called SOFT (self-organizing fuzzy technique) is proposed to solve the macro-cell placement problem. In SOFT, different criteria are simultaneously accounted by a novel fuzzy gain function which models expert knowledge to control the optimization process. The presented procedure is an adaptation of Kohonen's self-organization algorithm which is well suited for implementation on massively parallel architecture for fast computing. The MCNC benchmark examples are presented to verify the performance and feasibility of SOFT. Comparisons are made with the Hopfield network, SOAP and TimberWolf MC5.6. Experiments show that the proposed method yields an average of 17% improvement in total wire length compared with previous methods. Large size problems with 225 and 1024 arbitrarily-sized macrocells are also presented.
Minimizing the number of switchboxes for region definition and ordering assignment
(1996-03-01)
Yan, JT
;
Hsiao, PY
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
For a building block placement, the routing space will be fully defined into channels and switchboxes because the definition of switchboxes releases all the cycles in a channel precedence graph and further yields a safe routing ordering, However, switchbox routing is more difficult than channel routing. Due to the requirements in the routing phase, it is important for us to minimize the number of switchboxes in the definition of channels and switchboxes, In this paper, a region definition and ordering assignment (RDAOA) algorithm on minimizing the number of switchboxes is proposed. First, the routing space is modeled as a floorplan graph. According to the routing precedence in one ''T'' type junction, the graph is further transformed into a channel precedence graph, Hence, the problem of minimizing the number of switchboxes in region definition will correspond to the minimum feedback vertex set (MFVS) problem in the channel precedence graph. Second, based on the cyclic properties in a channel precedence graph, the MFVS problem is solved by the minimal-cycle phase and the long-cycle phase. All the minimal cycles and most of the long cycles are broken in the minimal-cycle phase, and the remaining long cycles are further broken in the long-cycle phase, As a result, fewer switchboxes are defined, and these channels and switchboxes are assigned to guarantee a safe routing ordering, The time complexity of the algorithm is proved to be in O(n) time, where n is the number of line segments in a given floorplan graph, Finally, several examples have been tested on the proposed algorithm and other published algorithms, and the experimental results show that our algorithm defines fewer switchboxes than other algorithms.
MPT-based branch-and-bound strategy for scheduling problem in high-level synthesis
(1998-11-01)
Hsiao, PY
;
Wu, GM
;
Su, JY
;
電機資訊學士班
;
Undergraduate Honors Program of Electrical Engineering and Computer Science
A branch-and-bound algorithm based on a maximum possibility table (MPT) is proposed to solve scheduling problems in high-level synthesis. Six efficient priority rules are developed as bounding functions in the algorithm. Extensions for real-world constraints are also considered, including chained operations, multicycle operations, mutually exclusive operations and pipelined data paths. Experimental results indicate that the MPT-based algorithm returns competitive scheduling results at significant savings in execution time as compared with other methods.
PLA-based Boolean factorization using ROBDD
(1995)
Hsiao, PY
;
Liaw, RT
;
Su, JY
;
資訊工程學系
;
Department of Computer Science
Planar constrained terminals over-the-cell router
(1997-03-01)
Shew, PW
;
Hsiao, PY
;
資訊工程學系
;
Department of Computer Science
The authors present a new routing model for over-the-cell channel routing. A graph theoretical algorithm is then proposed to solve the new problem, The algorithm has a complexity of O(nk(2)), where n is the number of nets and k is the number of columns in the channel. It achieved a routing area reduction of 71.5% for the PRIMARY 1 benchmark example from MCNC, using three-layer over-the-cell routing. To resolve a sub-problem, the authors also present an O(m nu) algorithm to find the maximum weight independent chord set in a circle graph with m chords incident to nu vertices, where two chords may share a common vertex.
Planar constrained terminals over-the-cell router
(1997-03-01)
Shew, PW
;
Hsiao, PY
;
資訊工程學系
;
Department of Computer Science
The authors present a new routing model for over-the-cell channel routing. A graph theoretical algorithm is then proposed to solve the new problem, The algorithm has a complexity of O(nk(2)), where n is the number of nets and k is the number of columns in the channel. It achieved a routing area reduction of 71.5% for the PRIMARY 1 benchmark example from MCNC, using three-layer over-the-cell routing. To resolve a sub-problem, the authors also present an O(m nu) algorithm to find the maximum weight independent chord set in a circle graph with m chords incident to nu vertices, where two chords may share a common vertex.
Unsupervised query-based learning algorithm and it's application to Kohonen's seif-organizing maps
(1995)
Chang, RI
;
Hsiao, PY
;
資訊工程學系
;
Department of Computer Science
Unsupervised query-based learning of neural networks using selective-attention and self-regulation
(1997-03-01)
Chang, RI
;
Hsiao, PY
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
Query-based learning (QBL) has been introduced for training supervised network model with additional queried samples, Experiments demonstrated that the classification accuracy is further increased. Although QBL has been successfully applied to supervised neural networks, it is not suitable for unsupervised learning models without external supervisors. In this paper, an unsupervised QBL (UQBL) algorithm using selective-attention and self-regulation is proposed. Applying the selective-attention, we can ask the network to respond to its goal-directed behavior with self-focus. Since there is no supervisor to verify the self-focus, a compromise is then made to environment-focus with self-regulation. In this paper, we introduce UQBL1 and UQBL2 as two versions of UQBL; both of them can provide fast convergence. Our experiments indicate that the proposed methods are more insensitive to network initialization. They have better : generalization performance and can be a significant reduction in their training size.
Using ordered binary decision diagrams to factorize multi-level logic
(1996)
Hsiao, PY
;
Liaw, RT
;
Su, JY
;
交大名義發表
;
資訊工程學系
A novel approach that employs ordered binary decision diagrams (OBDDs) is contributed to factorize multi-level logic functions by requiring as few literals as possible. A logic function with PLA format is represented as an OBDD form first. A heuristic decision method of variable ordering, called the order lookahead method, is derived for the construction of OBDDs. This method is based on the constant cofactor and the number of erasable logic terms for each input variable. The total execution time of the OBDD construction by the above ordering decisions is very fast for some MCNC benchmarks. With the above OBDDs, we introduce a simple yet effective graph manipulation, called EXT, to obtain a minimal number of literals in the Boolean function. This greedy EXT algorithm consists mainly of two phases. The first phase, called graph analysis,, identifies the similarities between nodes on the same level in the OBDD. The second phase, called tree analysis, utilizes the above features to extract the common parts of the nodes. The EXT procedure runs from the bottom level up to the top level of the OBDD. The computational complexity depends on the number of nodes in the OBDD. The results of simulations show that EXT has a very fast CPU execution time and a competitive literal ratio with other methods for some MCNC benchmarks. EXT will produce the smallest literal number, especially for structured or symmetric circuits.
Variable ordering for PLA-based ROBDD
(1995)
Su, JY
;
Hsiao, PY
;
資訊工程學系
;
Department of Computer Science
VLSI cell placement on arbitrarily-shaped rectilinear regions using neural networks with calibration nodes
(1995-12-01)
Chang, RI
;
Hsiao, PY
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
In VLSI or PCB layout, one often encounters a region that is either of rectilinear shape or can be approximated by a rectilinear region. Although many placement methods have been proposed, most of them are applicable only to rectangular regions. For these algorithms to be applied to a rectilinear region, two processing steps, region partitioning and rectangular region cell placement are necessary. Hence, the placement results are so far dependent on the locations of the regions partitioned and frequently become trapped in local minima. Recently, neural networks have been suggested as a new way to resolve the cell placement problem. This paper proposed a unified modeling method that uses a neural net model with additional calibration nodes to model rectilinear region cell placement. In this method, the ideal distance between cells is preserved to simultaneously minimize both the total wire length and the module overlap. Unlike traditional approaches, the proposed algorithm requires only a single processing step. Experiments have been conducted to verify the performance of the proposed algorithm. The total wire length obtained by our method is shorter than those generated by previous methods.
VLSI circuit placement with rectilinear modules using three-layer force-directed self-organizing maps
(1997-09-01)
Chang, RI
;
Hsiao, PY
;
資訊工程學系
;
Department of Computer Science
In this paper, a three-layer force-directed self-organizing map is designed to resolve the circuit placement problem with arbitrarily shaped rectilinear modules. The proposed neural model with an additional hidden layer can easily model a rectilinear module by a set of hidden neurons to correspond the partitioned rectangles. With the collective computing from hidden neurons, these rectilinear modules can correctly interact with each other and finally converge to a good placement result. In this paper, multiple contradictory criteria are accounted simultaneously during the placement process, in which, both the wire length and the module overlap are reduced. The proposed model has been successfully exploited to solve the time consuming rectilinear module placement problem, The placement results of real rectilinear test examples have been presented, which demonstrate that the proposed method is better than the simulated annealing approach in the total wire length, Furthermore, on the average, the central processing unit (CPU) time for the proposed method running on a sequential machine is 15 times faster than that required by the simulated annealing method, The appropriate parameter values which yield good solutions are also investigated.
VLSI circuit placement with rectilinear modules using three-layer force-directed self-organizing maps
(1997-09-01)
Chang, RI
;
Hsiao, PY
;
資訊工程學系
;
Department of Computer Science
In this paper, a three-layer force-directed self-organizing map is designed to resolve the circuit placement problem with arbitrarily shaped rectilinear modules. The proposed neural model with an additional hidden layer can easily model a rectilinear module by a set of hidden neurons to correspond the partitioned rectangles. With the collective computing from hidden neurons, these rectilinear modules can correctly interact with each other and finally converge to a good placement result. In this paper, multiple contradictory criteria are accounted simultaneously during the placement process, in which, both the wire length and the module overlap are reduced. The proposed model has been successfully exploited to solve the time consuming rectilinear module placement problem, The placement results of real rectilinear test examples have been presented, which demonstrate that the proposed method is better than the simulated annealing approach in the total wire length, Furthermore, on the average, the central processing unit (CPU) time for the proposed method running on a sequential machine is 15 times faster than that required by the simulated annealing method, The appropriate parameter values which yield good solutions are also investigated.