Engineering is an extremely exciting profession. Engineers are behind many of the advancements we are taking for granted today including computers, the Internet, smart phones, medical tools and cars. Engineers use science and math to create cool products and machines that make life an enjoyable living.
Engineering is not only n extremely exciting profession. It is a way of thinking. The word ‘engineer’ is from the Latin word ingenium, which shares the same root as the word ‘genius’. Certainly, every engineer would like to find optimal solutions to practical problems. However, the constraints of the problem-solving are of several, qualitatively different types. Often there is no formal way to find the best trade-offs.
Challenge to engineering optimization: NP hardness
For example, computational complexity presents a fundamental challenge to engineering optimization due to NP hardness. A problem is NP-hard if an algorithm for solving it can be translated into one for solving any NP-problem (nondeterministic polynomial time) problem. NP-hard therefore means “at least as hard as any NP-problem,” although it might, in fact, be harder.
Chip: computing exact wire length is an NP-hard problem.
For Green Electronics Manufacturing, a chip is composed of basic elements, called cells, circuits, boxes, or modules. They usually have a rectangular shape, contain several transistors and internal connections, and have at least two pins in addition to power supply. The pins have to be connected to certain pins of other cells by wires according to the netlist. A net is simply a set of pins that have to be connected, and the netlist is the set of all nets.
The basic placement task is to place the cells without overlaps in the chip area. A feasible placement determines an instance of the routing problem, which consists of implementing all nets by wires. The quality of a placement depends on the quality of a wiring that can be achieved for this instance. Creating Environmental Sensible Products, it is usually good if the wire length, the total length of the wires connecting the pins of a net, is as short as possible. The power consumption of a chip grows with the length of the interconnect wires, as higher electrical capacitances have to be charged and discharged, dissipating heat to the environment. From risk engineering perspective, signal delays increase with the wire length, impacting system integrity. Critical nets should be kept particularly short.
Thus, an important question is how to compute wire length without actually routing the chip. First note that nets are wired in different layers with alternating orthogonal preference direction. Therefore the `1-metric is the right metric for wire length. An exact wire length computation would require finding disjoint sets of wires for all nets, which is an NP-hard problem.
Seek Best Solutions under Constraints
To optimize engineering problem-solving, engineers are thinking similar to mathematicians in terms of problem formation. However, in many branches of mathematics, finding best solution is not essential. For a mathematician, finding any proof is often a sucess. Engineers, by contrast, are not satisfied with existence proofs. Getting something to work is inadequate. The product has to best satisfy customer requirements. Even in simple problem solving, the engineer looks for evidence that the space of possible solutions was adequately searched, and the chosen solution validated to be optimal.
Facing the challenge of NP-Hardness, engineers provide explanations to justify their choices based on their judgments. Engineering thinking develops explanations that identify and validate the problem solving under constraints. Engineering thinking involves induction (analogical reasoning) as well as deduction. Comparing with science, engineering has often been considered an irrational genre, more expressive than logical, more meditative than given to coherent argument. All innovative engineers are thinkers. While the styles of innovative engineering thinking are distinctive, they are characterized by:
- Modeling: model-based ideas.
- Rethinking: reflection-based innovation.
- Experimenting: from rearranging to renovation.
- Picture thinking: from image to assertion.
In engineering decisions concerning constraints and uncertainty, the engineer draws on similar previous problem-solving. Analogical reasoning is actually at the heart of Engineering Thinking, requiring a rich set of source analogs from which to reason, similar to a poet experiments with plot to characterize life’s unfolding.
https://www.crcpress.com/Cellular-Manufacturing-Mitigating-Risk-and-Uncertainty/Wang/9781466577558
drjohnxwang 