doPlan() performance

[Bernd Walter]

As mentioned in another thread I'd played with a LED board of 100 identic LEDs and all 4 nozzles enabled for that part.
It didn't work.
After analyzing it is clear that doPlan() just blows up with the cartesian product block.
Each nozzle gets a possible part list of 100+1 (null) entries.
The cartesian is something around 104+E6 entries.
A small set of them gets filtered, but the rest has to be sorted.
And it's even done for each individual cycle, but it my case it worked fast with 3 nozzles,
but didn't work at all with 4.
Symptoms were that it sucked CPU time on all my 4 cores for several minutes, then CPU
time went down without ever getting into Nozzle for loop next in code.
I don't know where exactly it blows up, but it is already clear that this way won't scale.
Not sure if I will get any critical sized cartesian with my real world jobs, but nevertheless
it can bite any time.
I can see the intention of doing it that way, but what about the following idea?
Sorting the individual nozzle job lists by byFewestNozzleChanges and maybe part height.
Then sweep through the first entries of the nozzle lists, similar as the current cartesian filter.
If the part is already the first element on the checked nozzle list delete it and retest with the
new first element.
Finally take all the first elements as the cycle job result.
There are still some sorts to be done, but only on the much smaller nozzle lists.
I assume noone ever have jobs with anything near to 104+E6 parts.
It may not be a perfect result, but neither is the current way.
And it will scale much better with more nozzles and components.

[Jason von Nieda]

Hi Bernd,

This makes sense. Most of my testing is done with jobs of < 100 parts and only 1 or 2 nozzles. At 4 nozzles, certainly, that cartesian product is going to be overly large.

Your proposed change makes sense to me, but I will have to really trace it out to see if it caused any problems. Some of the things that have to be considered are:

* Multiple of the same parts being placed on the same cycle.

* Multiple identical nozzle tips.

* Nozzle tips for which there is no current solution.

* Optimizing for most nozzles used per cycle.

If you have the ability to implement your proposed change, I'd be interested to hear how it works and see the code.

In the near future this will become mostly moot. We'll be switching to a system where placement order is just taken from the order of the placements list and only trivial planning will happen on each cycle. 

Jason

--
You received this message because you are subscribed to the Google Groups "OpenPnP" group.
To unsubscribe from this group and stop receiving emails from it, send an email to openpnp+u...@googlegroups.com.
To post to this group, send email to ope...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/openpnp/0cb4a3a4-95b6-4f4a-b046-1dfbe059d276%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Bernd Walter]

On Wednesday, October 4, 2017 at 3:41:52 PM UTC+2, Jason von Nieda wrote:

Hi Bernd,

This makes sense. Most of my testing is done with jobs of < 100 parts and only 1 or 2 nozzles. At 4 nozzles, certainly, that cartesian product is going to be overly large.

Your proposed change makes sense to me, but I will have to really trace it out to see if it caused any problems. Some of the things that have to be considered are:

* Multiple of the same parts being placed on the same cycle.

* Multiple identical nozzle tips.

* Nozzle tips for which there is no current solution.

* Optimizing for most nozzles used per cycle.

Some points might be hard to do.
E.g. it doesn't make much sense to fill the nozzles with parts on the left and the right side of the board.
Mixing fast moveable with slow moveable parts, ...
All in all I think a not so sophisticated optimization might be better than trying a perfect one, because
in the end you really need a big cartesian to find the best order.

If you have the ability to implement your proposed change, I'd be interested to hear how it works and see the code.

I can try to get it running.
 

In the near future this will become mostly moot. We'll be switching to a system where placement order is just taken from the order of the placements list and only trivial planning will happen on each cycle. 

Ok.
 

[Cri S]

how long it takes ?
I do the planning of job during fiducial recognizing.
Further i have the option to sequence the boards inside panels.
This is sometimes more efficient and precise.

>> On Wed, Oct 4, 2017 at 8:05 AM Bernd Walter <be...@bwct.de <javascript:>>

>>> email to openpnp+u...@googlegroups.com <javascript:>.

>>> To post to this group, send email to ope...@googlegroups.com

>>> <javascript:>.

>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msgid/openpnp/0cb4a3a4-95b6-4f4a-b046-1dfbe059d276%40googlegroups.com
>>>

>>> <https://groups.google.com/d/msgid/openpnp/0cb4a3a4-95b6-4f4a-b046-1dfbe059d276%40googlegroups.com?utm_medium=email&utm_source=footer>
>>> .

>>> For more options, visit https://groups.google.com/d/optout.
>>>
>>
>

> --
> You received this message because you are subscribed to the Google Groups
> "OpenPnP" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to openpnp+u...@googlegroups.com.
> To post to this group, send email to ope...@googlegroups.com.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/openpnp/3952dc3f-c6fe-458f-9362-d6a63f2a23e2%40googlegroups.com.

[Bernd Walter]

On Saturday, October 7, 2017 at 6:05:33 PM UTC+2, Cri S wrote:

how long it takes ?

I havn't started yet.
So far this problem only had been problematic for this test and I have a lot of other problems to solve.
 

[Cri S]

If you have problem, i could adapt my code to the fsm .in order to
drop the collect.java
code.

My code does the following:
placements is divided into 4 lists.
place (<=3mm) , todo (<=8mm), sequence (>8mm) and priority.
priority holds the parts that need to be placed before the parts
inside todo list can be
placed based on the height.
Every part inisde todo list that don't have priority parts are
moved to place list.
sequence list are placed in sequence based on the height, lower
height first, and beside
3mm parts with radius less then 5.5mm no other parts are allowed.
Exception exist for diameter bigger as 50 mm and height more then
18mm as then no
other component is allowed.
With 21.4mm clearance to pcb the follow limits exists:
For parts with diameter >50mm height limit is 12 mm .
For parts with diameter <=50mm height limit is 26mm
With path planning, limit is 38mm.
Path planning require support for softlimits included into grbl driver.

2017-10-08 14:18 GMT+02:00, Bernd Walter <be...@bwct.de>:
>
>
> On Saturday, October 7, 2017 at 6:05:33 PM UTC+2, Cri S wrote:
>>
>> how long it takes ?
>>
>
> I havn't started yet.
> So far this problem only had been problematic for this test and I have a
> lot of other problems to solve.
>
>
>> I do the planning of job during fiducial recognizing.
>> Further i have the option to sequence the boards inside panels.
>> This is sometimes more efficient and precise.
>>

>> 2017-10-04 16:24 GMT+02:00, Bernd Walter <be...@bwct.de <javascript:>>:

>> https://groups.google.com/d/msgid/openpnp/3952dc3f-c6fe-458f-9362-d6a63f2a23e2%40googlegroups.com.
>>
>>
>> > For more options, visit https://groups.google.com/d/optout.
>> >
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "OpenPnP" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to openpnp+u...@googlegroups.com.
> To post to this group, send email to ope...@googlegroups.com.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/openpnp/8f577720-3242-420d-b5c0-90e1abf9a1bf%40googlegroups.com.