Wednesday December 17, 2014

Solving the CAD concurrency problem

Earlier this week, I was doing some software testing on my lab machine. It’s a really nice Z1, on loan to me from HP. It has an 8-core high-end Intel processor. I brought up the process monitor as I worked, and watched, somewhat amused, as Autodesk Inventor pegged one core at 100% for several minutes, while the other cores sat there, doing almost nothing.

isketch5m

This is a really big sketch. CAD programs don't like these.

It wasn’t Inventor’s fault. Well, not really. The particular test I was doing was designed to push the 2D sketcher in Inventor to its limit. It contained 1024 triangles, connected with over 3072 constraints (I didn’t count exactly.) That sketcher uses a component called 2D DCM (Dimensional Constraint Manager), part of the D-Cubed group of software components, developed and sold by Siemens PLM Software.

Many well-known CAD programs use D-Cubed software. It’s the stuff that, when you push and pull on a sketch (or a CAD model) figures out what you’re trying to do, and calculates the resulting shape. 2D DCM is often called a “constraint manager,” or a “solver.” Built into its heart are a bunch of very complicated algorithms for solving systems of linear equations. It’s PhD level stuff.

In the case of my testing, it was 2D DCM that used all the power of one core, but ignored the other cores in my computer – essentially, leaving 7/8 of the power that HP built into the computer untapped.

So, here’s the question: Why doesn’t Siemens PLM just tell their programmers to fix 2D DCM, so it can use multiple cores? Why not rewrite it to support concurrency? If they did that, it’d solve a lot of other problems at the same time—for example, it would make creating cloud based CAD systems, that run across multiple processors and servers, a lot easier to implement.

As a start, 2D DCM has been thread-safe since 2009. A CAD system can run multiple instances of the program on parallel processors, without any significant performance hit.

So it does run on multiple cores. Problem solved?

Hardly.

In my test, I’d created a 2D sketch in Inventor. where moving any one node or edge required the system to recalculate all of the lines in all of the triangles.  All 1024 of them.  There were no independent constraints, where making a change would not affect other geometry. They were all interlinked.

Suppose Autodesk’s programmers had set up Inventor to use multiple instances of 2D DCM on multiple cores. How could a problem such as mine be partitioned to use those multiple instances?

The answer is: it couldn’t. Running 2D DCM on multiple cores allows those multiple instances to solve independent constraints. Not interlinked constraints.

Let me see if I can paint a picture of the problem. When I was a kid, I used to play a game called pick-up sticks. The idea was to dump out a bunch of long sticks on the floor (or table), creating a tangled pile. Each player, in turn, would remove a stick from the pile without disturbing the remaining ones.

pic117168 md

Imagine several people playing pick-up sticks, but instead of waiting in turn, all of them trying to remove sticks at the same time. Concurrently. That’s pretty analogous to the problem of partitioning the data in a sketch in a way that it’s possible to use parallel solvers. There’s no easy way of partitioning the equations representing the system of constraints in such a way that they can be solved in parallel.

2D DCM has been around for quite a long time, as CAD component software goes. When it was designed, the programmers likely looked at the issue of parallel computing, shuddered, and decided to focus on making the software actually work right in the first place. It probably made sense at the time: Multicore processors, and even parallel computers, were rare.

Over the years, some things have changed. Multicore, parallel processors, clusters, and cloud computing are now commonplace. And there have been advances in math. Do a search on Google Scholar for “parallel solutions of linear systems” and you’ll get a lot of results. Still, adding parallel support into a tool like 2D DCM isn’t just a matter of writing some lines of code. It might involve tearing it down to the ground, and rebuilding it with a completely new architecture.

Is Siemens willing to invest what would likely be a princely sum in rebuilding their D-Cubed products from the ground up? I can’t answer that question. If I asked the folks at Siemens, and they told me, I’d not be able to tell anyone else. Trade secrets, you know. But I can say that I hope they are looking at this problem, because it’s one of the key limitations that get in the way of developing next-generation high-performance CAD software.  The kind that can run on multiple cores, multiple processors, clusters, or the cloud.

I wrote this post in response to a commenter, who was raising the issue of the lack of multicore support in current CAD systems. I think his concern is valid, but I wanted to make the point that this is not a simple problem to fix, whether in geometric constraint managers, or geometric modeling kernels. It’s like the pick-up sticks problem: Really difficult, even if you throw big piles full of money at it, and wave fat paychecks at PhD mathematicians.

Still, there are people working on these problems. Next week, I’ll be writing a bit about Cloud Invent, a tiny company that may have made a breakthrough in geometric constraint modeling.

 

Pick-up sticks image courtesy David Namaksy, boardgamegeek.com

  • http://camzone.org/ Daniel Santos

    Thanks Evan for bringing some light to this subject. It’s common to believe that re-write systems to use multi-cores is an easy task or just a matter of money, but the fact is that hardware and software not always evolve in the same pace… in some areas software moves faster and in some others the hardware is ahead of the software’s time.

    Great analogy with the “pick-up sticks” game. That is pretty much how it is.

  • Rachel Berry
  • Rachel Berry

     btw I am now a Citrix employee but this is just made as a personal observation and isn’t linked to my role or the company’s policies….

  • http://jonbanquer.blogspot.com/ Jon Banquer

    Cloud Invent are the only ones I’m aware of who are willing to talk about what the real problem is and offer proof of a solution. Unfortunately, I don’t see any dates on meeting their announced goals so it’s impossible to see what stage they are at:

    http://www.cloud-invent.com/Nimbo.aspx

    Hopefully when you write about Cloud Invent more details of where they are at will be made available.

    It sure would be nice if others besides Cloud Invent were willing to discuss how they plan to fully support multi-core processors. I don’t think this is an issue that CAD companies can continue to pretend isn’t a major problem much longer.

    Jon Banquer
    San Diego, CA
    http://cadcamtechnologyleaders.blogspot.com/

  • http://www.yamanoor.com/ Yamanoor Srihari

    This is very educative! 

  • http://jonbanquer.blogspot.com/ Jon Banquer

    It’s odd that Cloud Invent has been silent for about a year. I wonder if they have signed an agreement, sold their technology or are in protracted negotiations with someone.

    Jon Banquer
    San Diego, CA
    http://cadcamtechnologyleaders.blogspot.com/

  • http://evanyares.com Evan Yares

    Here’s my impression:  There’s an old saying in programming that the first 90% of the problem takes the first 90% of the time, and the last 10% of the problem takes the other 90% of the time.

    Cloud Invent’s technology is really interesting, but it takes a lot of time to build a commercial-grade solver.  Years.

  • http://jonbanquer.blogspot.com/ Jon Banquer

    I have always found it interesting that most CAD and CAM uses spend so much of their time focusing on symptoms rather than the cause of their problems and that most CAD and CAM users expect easy answers where there are none.

    If Cloud Invent never delivers anything they have still opened up discussion on issues that no one in the CADCAM business wanted opened up and for that I’m very thankful!

    I also think those who see CAM only by the numbers of installations and frequently dismiss CAM would due very well to remember that CAM is now easily leading CAD when it comes to multi-core processor support.

    Jon Banquer
    San Diego, CA
    http://whatwrongwiththecadcampress.blogspot.com/p/refusal-to-report-truth-on-siemens.html

  • http://twitter.com/DevonSowell DevonSowell

    Very informative, thanks for posting.

  • Dadcadd

    nice post and blog too

  • Pingback: Cheetah, Creo, and 2D geometric constraint solvers | 3D CAD Tips()

  • Ryan

    I’m sorry to
    be the bearer of bad news to all of you but you should all know that D-Cubed:

    1) support
    multi-processors and;

    2) ”
    Version 58 introduces support for instances. Instances are copies of groups of
    geometries, such as profiles, where each instance is constrained to have the
    same shape, and where there can be any separation and orientation between each
    instance..The new functionality complements the pattern constraint that has
    been supported by the 2D DCM for some time, which enables geometry to be
    constrained in regularly repeating linear or radial arrays.”

    I do know
    that this patterning capability has it’s roots in a project that I help
    establish with Siemens and PLM World Modeling & Assy Special Interest
    Group!

    In the case
    above, I would have to say that you are seeing the effects of Autodesk not
    incorporating the new functionality of 2D DCM in their software, not a deficiency
    in D-Cubed!

    Ryan
    Minneapolis, MN