China
Africa
Explore chapters and articles related to this topic
Static Timing Analysis
Published in Louis Scheffer, Luciano Lavagno, Grant Martin, EDA for IC Implementation, Circuit Design, and Process Technology, 2018
Note that the skews at the primary inputs and the primary outputs may be set to zero under the assumption that they cannot be controlled or adjusted. For a constant value of P, the constraint matrix for this problem reduces to a system of difference constraints [20]. For such a system, it is possible to construct a constraint graph. The vertices of the constraint graph correspond to the xi variables, and each constraint xa – xb ≥ c corresponds to a directed edge from node b to node a with a weight of c. If P is achievable, then a set of skews that satisfies P can be found by solving the longest path problem on this directed graph. The clock period P is feasible, provided the corresponding constraint graph contains no positive cycles.
Coupling Noise
Published in Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, 2008
Rajendran Panda, Vladimir Zolotov, Murat Becer
In case of functional noise, after logic constraints generation, noise analysis is performed for every cluster for its respective noise type. If the generated logic constraints are made of two variable relations only, a constraint graph is formed based on generated SLIs, and then maximum weighted independent set (MWIS) problem is solved [18]. If the constraints involve many variables [21], then the constraint graph turns into a hypergraph. Therefore, instead of the constraint graph, a reduced order binary decision diagram (ROBDD) of the noise cluster constraints is constructed. Using the characteristic ROBDD of the noise cluster, the maximum noise of a given type is calculated by finding the maximum weighted set of the aggressors for which simultaneous switching of the same type is not prohibited. In Figure 34.13, examples for a constraint graph and a constraint hypergraph are given.
Channel Routing with Constraint Logic Programming and Delay
Published in Takushi Tanaka, Setsuo Ohsuga, Moonis Ali, Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, 2022
Two constraint graphs are created based on the given set of nets: one directed graph called a vertical constraint graph Gv and one indirected graph called a horizontal constraint graph Gh. In Gv, each vertex corresponds to a net and each arc from vertex u to vertex v means that net u must be placed above net v if they are placed in the same horizontal layer. The relation above does not necessarily reflect the physical configuration of tracks. A track with number t1th is said to be above another track with number in the same layer if t1 is greater than t2.In Gh, each vertex corresponds to a net and there is an edge between two vertices u and v if net u and net v cannot be placed on the same track. Figure 5 depicts the constraint graphs for the set of nets shown in Figure 3. There is an arc from vertex 1 to vertex 5 in Gv because t5 is included in N1 and b5 is included in N5. If N5 is placed above N1 or on the same track as N1 in the same horizontal layer, then the vertical segments on the fifth column will overlap. There is an edge between vertex 1 and vertex 2 in Gh because the segment (2,5) connecting the two farthest terminals in N1 and the segment (1,6) connecting the two farthest terminals in N2 overlap each other. Notice that the relation above is not transitive unless there is only one vertical layer in the given channel. For example, in a 2HV channel, N4 can even be placed below N8 in the same horizontal layer if N9 is placed in a different horizontal layer.
Operational aircraft maintenance routing problem incorporating cruise speed control
Published in Engineering Optimization, 2022
Qing Zhang, Felix T. S. Chan, S. H. Chung, Xiaowen Fu
The ACO metaheuristic is inspired by the foraging behaviour of ant colonies, which involves communicating via pheromones deposited along the way to discover the shortest route from a nest to a food resource. The pheromone information reflects the experience of previous ants in route searching and changes dynamically to provide guidance for future ants. To employ an ACO algorithm to tackle combinatorial optimization problems, the problem must be modelled as finding the shortest path on a weighted and constraint graph. Then, ants move over the graph, search for good paths using pheromones and problem-specific heuristic information, and deposit pheromones along the promising routes. In general, the ACO algorithm is composed of two fundamental procedures: route construction and pheromone update. Next, the ACO algorithm for the OAMRP incorporating cruise speed control will be described in detail based on the two procedures. The flowchart of the proposed algorithm is illustrated in Supplemental Material 5.
Urban layout optimization in a city network under an extended quadratic assignment problem framework
Published in Transportmetrica A: Transport Science, 2022
Jialu Fu, Xianting Huang, Lu (Carol) Tong
Table 1 compares key elements in urban layout models. Specifically, Barber (1976) presented an urban land use optimization model, which simultaneously considers critical urban planning and transportation criterions, such as land-development costs, residential accessibility and energy consumption in transportation. By applying an interactive modelling approach, Liége and Hégron (1997) described the urban layout process as an associated constraint graph and obtained optimal solution through the constraint propagation algorithm. To synchronously consider land use and transportation network, Feng and Lin (1997) first proposed the Sketch Layout Model (SLM) and improved this model by adding various other elements, e.g. transportation network design (Feng and Lin 1999), public facility layout (Feng and Lin 2000) and trip distribution/assignment model (Feng and Lin 2003). In the practical application, UrbanSim (Waddell 2002) can be used to determine the discrete choices (e.g. the household and employment location) considering the real estate development and interaction with travel models etc. The other related modeling focuses include energy consumed by transportation and buildings (Keirstead and Shah 2011), urban form alternatives and walkability measures (Pakha and Reinhart 2012), integrated land-use and transport model system (Ouyang and Lam 2010; Yim et al. 2011; Pendyala et al. 2012), combined distribution and assignment (Yao et al. 2014), population allocation and network enhancement (Xu et al. 2016), as well as comprehensive urban layout simulation (Lyu, Han, and Vries 2017).
Multi-Semantic Alignment Graph Convolutional Network
Published in Connection Science, 2022
Jisheng Qin, Xiaoqin Zeng, Shengli Wu, Yang Zou
The features of a node in the ideal environment can be utilised to determine its class. For the semi-supervised classification task, graph structure-based propagation can pass semantic information from labelled to unlabelled nodes because we assume that neighbouring nodes usually belong to the same class. However, M. Liu et al. (2020) proved that the class of nodes is determined by their features rather than their topology. Therefore, based on X. Yang et al. (2021), we add the filtering of nodes from the perspective of features and then obtain the node features from another perspective by transformation. Finally, we adopt the semantic alignment operation for feature learning during constraint graph propagation.