Process for Predicting Structural Performance of Mechanical Systems

This invention relates generally to the field of predicting structural performance of mechanical systems, and more specifically to processes amenable to multiprocessor computers for locating surface contacts that affect structural performance.

Processes using Lagrangian finite elements are widely used for predicting the structural performance of mechanical systems (e.g., impact damage to shipping containers or vehicles). Present processes are not suited to efficient practice on multiprocessor computers because the present processes do not load balance well on multiprocessor computers. A finite element mesh representing the mechanical system is typically partitioned on the multiprocessor so that each processing unit owns a localized region of the finite element mesh. This mesh partitioning is optimal for finite element determinations of stress, strain, and force because each processing unit only needs to communicate with neighboring processing units. However, contacts can occur between finite elements owned by any two processing units (e.g., as metal crumples during impact). Accordingly, present processes require a search across all the processing units for contact between surfaces. The search does not make efficient use of multiprocessor resources, and does not provide substantially equal work for all the processing units in the multiprocessor.

The inefficient location of contacts has limited the application of present processes for predicting the structural performance of mechanical systems. A process better suited to multiprocessor application is needed to predict the structural performance of more complex mechanical systems.

The present invention provides a process for predicting the structural performance of a mechanical system. The invention provides an improved process for locating surface contacts in the mechanical system. The improved process is more efficient than present processes, and is well suited for use on multiprocessor computers.

The present invention represents the surfaces of the mechanical system as a plurality of surface elements. Each surface element represents a surface of the mechanical system that will not contact itself. Together, the surface elements represent all the surfaces in the mechanical system. If the mechanical system shears or otherwise creates additional surfaces, then additional surface elements can be added to represent the new surfaces.

The present invention determines the velocity of each surface element from the forces acting upon it for a selected time interval, ignoring the effects of surface contacts. Small time intervals can increase the accuracy of the prediction. The velocities can be determined by a variety of processes, including, for example, finite element modeling. After the velocities are determined, the resulting positions of the surface elements are compared to determine if any surface element will contact any other surface element. If so, then the present invention imposes forces on the surface elements so that they will not pass through each other. The resulting forces are added to those used for determining the surface element velocities for the next time interval.

The present invention groups the surface elements according to their position in the volume occupied by the mechanical system. Because each surface element moves only a limited distance in each time interval, the process can check for contacts only with surface elements in the same or neighboring groups. After each time interval, the surface elements can be re-divided to keep the groups substantially the same in size and to keep surface elements grouped by their current position in the volume. For mechanical systems with many surface elements, the present invention can dramatically reduce the complexity of the search for surface elements contacts. This reduction in complexity can provide faster predictions when implemented on a multiprocessor computer.

The accompanying drawings, which are incorporated into and form part of the specification, illustrate embodiments of the invention and, together with the description, serve to explain the principles of the invention.

FIG. 1(a-c) is a timed sequence illustrating two blocks coming into contact.

FIG. 2(a-c) is a timed sequence illustrating a cylinder being deformed by a moving plate with surface element grouping according to the present invention.

FIG. 3(a-c) is a graphical depiction of surface element grouping according to the present invention.

FIG. 4 is a flow diagram of a performance prediction process according to the present invention.

FIG. 5 is a flow diagram of a surface element grouping process according to the present invention.

FIG. 6 is a flow diagram of a process for unstructured communication according to the present invention.

The present invention provides an improved process for predicting the structural performance of a mechanical system. The improved process groups surface elements, representative of the surfaces in the mechanical system, so that a search for contacts is less complex and more efficient than required in present processes.

A mechanical system M, depicted in FIG. 1(a-c), comprises two blocks A, B. At an initial time t.sub.0, in FIG. 1a, the two blocks A, B are separated from each other. The surface of each block A, B is divided into a plurality of surface elements such as surface elements A1, A2, B1, B2, B3, etc. Block A is moving toward block B. FIG. 1b shows the same blocks A, B at a first time t.sub.1, after the initial time t.sub.0. Block A is about to contact Block B. FIG. 1c shows the two blocks at a second time t.sub.2, after the first time t.sub.1. Block B contacts Block A and applies force thereto. Any process predicting the performance of the mechanical system M must compare the locations of surface elements to check for contacts. In FIG. 1c, surface element A1 contacts surface element B3. Such process predicting the mechanical system's M performance can impose forces on the two blocks A, B to prevent the surface elements A1, B3 from passing through each other. The imposed forces can be used to predict the blocks' A, B further performance by processes such as finite element modeling.

In the mechanical system M shown in FIG. 1, a small number of surface elements are to be checked for contact. More complex mechanical systems can require many more surface elements to accurately predict their performance. Checking for contacts by exhaustively searching all possible pairs of surface elements can be prohibitively expensive and time consuming. The present invention provides an improved process for grouping surface elements so that the search for contacts is efficient.

FIG. 2(a-c) shows a mechanical system comprising a cylinder C and a plate P. Initially, shown in FIG. 2a, the cylinder C and the plate P are just in contact. The plate P is moving toward the cylinder C. Every surface in the mechanical system M2 is divided into a plurality of surface elements. Each surface element represents a portion of a surface small enough that it will not contact itself. A process according to the present invention divides the mechanical system into regions, where each region represents a contiguous portion of the mechanical system and where all the regions contain substantially the same number of surface elements. The surface elements are grouped so that all the surface elements in a region belong to the same group. Accordingly, surface elements near the top left of the figure belong to one group 201, while surface elements near the bottom left belong to another 202. The number of regions is dependent on the particularities of the mechanical system and on the apparatus used to practice the invention; for a multiprocessor computer the number of regions can be equal to the number of processing units. After a specified time interval, each surface element is checked for contact with every surface element in its region. If the surface element moved out of the region, then the surface element is checked for contact with surface elements in the region corresponding to the surface element's new position. As long as the time interval and surface element velocities do not permit surface elements to travel farther than one region per time interval the search for contacts does not need to consider surface elements in other regions. For large number of regions, considerable reduction in the time required to locate surface element contacts can result.

In FIG. 2a the plate P and the cylinder C have just come into contact. Surface elements on the bottom of the plate P contact surface elements on the top of the cylinder C. For each surface element contact, a force is applied so that the surfaces will not pass through each other. The forces are then used to predict the performance of the material of the plate P and the cylinder C for the next time interval.

In FIG. 2b the plate P has crushed the cylinder C. The system in FIG. 2c is the system of FIG. 2b after many time intervals. The location of contacts and application of suitable forces, and prediction of the material response to the forces are repeated at each time interval.

In FIG. 2b the surface elements have moved significantly from their original locations. Accordingly, the division into regions is different. Some of the surface elements 203, 204 that were originally in different regions are now in the same region since they have moved closer together as the prediction process proceeds. Because the subdivision into regions changes as the surface elements move, the search for contacts can still be limited even though surface elements have moved.

In FIG. 2c the plate P has more completely crushed the cylinder C after many more time intervals. The surface element grouping is different from that in FIG. 2b since the surface elements have changed position in the volume. The surface elements are still grouped according to their position, however, so the search for contacts is still efficient.

The surface elements can be grouped by considering each element's location in the volume occupied by the mechanical system. A first region is formed that includes all the surface elements. The first region can be divided into two sub-regions, each having substantially the same number of elements. The division is made along a plane through the first region. All the surface elements in a sub-region are assigned to the same initial group. The two sub-regions can then be divided into new sub-regions by different planes extending through the region of the volume associated with the group, and the surface elements assigned to new groups based on the new sub-regions.

FIG. 3(a-c) shows several steps of this process using a two dimensional representation of the volume and lines for the planes of region division. The figure represents surface elements and their locations by points in the plane such as point E. In FIG. 3a the first group G1 of surface elements is divided into two groups G11, G12 by a line. In FIG. 3b each of the two groups G11, G12 is divided by new lines, dividing the groups G11, G12 into four new, substantially equal groups G21, G22, G23, G24. FIG. 3c shows the result of further dividing the groups of FIG. 3b. The resultant division has substantially the same number of surface elements in each region, and each group of surface elements contains all the surface elements from the same region of the volume. The search for contacts therefore can include only surface elements in the current or neighboring regions.

Forces are applied to the contacting surface elements to prevent their overlap or penetration. The applied forces are used in the next time interval in the prediction of forces and velocities. Because each surface element can move only a finite distance in one time interval, the surface element grouping from the last time interval is close to the surface element grouping required for the current time interval. Small adjustments in the grouping can be more efficient when practicing the process on a multiprocessor computer.

The present invention can be practiced using a multiprocessor computer such as the Intel Paragon as described in Paragon System User's Guide, Intel Corporation, Beaverton, Oreg. (April 1996), incorporated herein by reference. "A Paragon system can have up to more than 2000 nodes. Some nodes are equipped with a SCSI interface, Ethernet interface, or other I/O connection. These nodes manage the system's disk and tape drives, network connections, and other I/O facilities. Nodes with I/O interfaces communicate with the other nodes over the node interconnect network. However, this access is transparent: processes on nodes without I/O hardware can access the I/O facilities using standard OSF/1 system calls, just as though they were directly connected. Nodes with I/O interfaces are otherwise identical to nodes without I/O interfaces, and can run user processes." The prediction of forces and velocities for each time interval can be accomplished with a Lagrangian finite element program. A suitable program is described by Taylor and Flanagan in "PRONTO-3D: A Three-Dimensional Solid Dynamics Program," SAND87-1912, Sandia National Laboratories, incorporated herein by reference. A mechanical system is first represented by a plurality of material elements and surface elements and by models for the materials in the mechanical system.

FIG. 4 shows the flow of operations for prediction of the mechanical system's performance after a time interval. The equations of motion are integrated for the material elements and surface elements 401. The strain rate can then be computed based on the motion of the material elements 402. The stress rate can then be computed based on the strain rate and the material models 403. From these the internal forces acting on the material elements can be computed 404. From the internal forces, the accelerations of the material elements and surface elements can be computed. From the accelerations and the time interval the locations of the surface elements after the time interval can be predicted 405. The predicted locations of the surface elements can then be checked for contacts 406. For each contact, forces can be applied to the corresponding surface elements and material elements to prevent the surface elements from passing through each other 407. Those skilled in the art will appreciate that variations on the above sequence are possible. The predicted locations of the surface elements can be displayed at selected times, or can be recorded for subsequent use.

The search for potential contacts can be accomplished with a surface element grouping process as described above. One efficient process for dynamically regrouping the surface elements is recursive coordinate bisectioning (RCB), as described by M. J. Berger and Bokhari in "A Partitioning Strategy for Nonuniform Problems on Multiprocessors," IEEE Trans. Computers, C-36, pages 570-580 (1987), incorporated herein by reference. One pass through the grouping process can involve the steps shown in FIG. 5. An axis through the volume can be chosen 501. Then, a plane or other surface can be positioned on the axis to divide the volume into two parts 502. Each side of the division can have corresponding processing units. Each processing unit can have information about surface elements. The surface elements can then be divided into two groups by sending surface element information to processing units corresponding to the side of the division where each surface element resides 503. This can be done by sending surface element information for each surface element that currently resides locally but is located on the far side of the division to processing units corresponding to the far side of the division 504, and receiving information about surface elements that currently reside on processing units corresponding to the far side of the division but that lie on the near side of the division 505. If the surface elements have been divided into enough groups, then the grouping process can stop 506. If not, then grouping process can continue, for example, by recursing through the process with each subgroup result from the previous grouping 507, 508. The number of surface element groups can be chosen to maximize load balance, minimize communication costs, maximize search efficiency, or some other characteristics of the process. Grouping the surface elements after one time interval of movement can begin with the groupings from the previous time interval. Surface element information does not need to be sent unless new group boundaries and surface element movement have changed the surface element to group to processing unit correspondence. Relatively slow surface element movement and short time intervals can therefore reduce the amount of communication required for surface element grouping.

Practicing the invention on an Intel Paragon multiprocessor requires unstructured communication. For example, the communication of surface elements after division into groups requires unstructured communication. Unstructured communication required to practice the invention can be implemented as shown in FIG. 6. Each processing unit determines which other processing units it must send information to, called a destination processing unit. A vector of 0s and 1s is formed with a 1 at each vector index corresponding to a destination process and 0s at all other vector indices 601. The vector can then be folded over all the processing units, generating an efficient summation of all the vectors 602. The number of receives required at each processing unit can be determined from the number in the corresponding vector index. Each processing unit can then initiate the appropriate number of receives to receive short messages defining the message parameters of the full messages 603. Each processing unit can also send short messages defining the parameters required for the full message to each destination processing unit 605. After the message parameters are received, each processing unit can initiate the appropriate receives for the full messages 604, and can send the full messages 605. Those skilled in the art will appreciate that other messaging processes might be used with other performance objectives or other multiprocessor computer systems.

A specific embodiment of the present invention using an Intel Paragon multiprocessor is described in "A New Parallel Algorithm for Contact Detection in Finite Element Methods," Hendrickson, Plimpton, Attaway, Vaughan, Gardner, Proceedings of the High Performance Computing '96 Conference (New Orleans, April 8-11, 1996, pp. 170-6), incorporated herein by reference.

The particular sizes and equipment discussed above are cited merely to illustrate particular embodiments of the invention. It is intended that the scope of the invention be defined by the claims appended hereto.