kicad-developers team mailing list archive

[Carl Poirier <carl.poirier.2@xxxxxxxxx>]

Hi Maciej,

Your last changes allow a complete independence of the loop iterations
in RN_DATA::Recalculate( int aNet ).

I have almost a 2x speedup on a Core i7-4770 with the very simple
parallelization in the attached patch. I was expecting more, though. There
seems to be a bottleneck somewhere. I have a question, however. Did you
want to speedup the computation when you move the part? From what I
see, RN_DATA::Recalculate( int aNet ) is run only when the user loads the
board. Am I missing out on something?

BTW, I've included in the patch some output to measure computation time,
which obviously is not meant to be committed. I have also added the
required build flag at the top of the CMakeLists.txt, because I don't know
exactly where it should go in it.

Carl


On Tue, Jan 28, 2014 at 4:51 AM, Maciej Sumiński <maciej.suminski@xxxxxxx>wrote:

> Hi Jean-Pierre,
>
> I am done with the changes that would let me rely on the net codes in
> other parts of code. I did my best to perform tests and put comments to
> each commit, so they could be easier to understand and verify.
> Could you please have a look at the lp:~cern-kicad/kicad/netnames branch?
> If you think the proposed changes do not break anything, I would be
> grateful for merging the branch. Thank you in advance.
>
> Regards,
> Orson
>
> On 01/11/2014 05:31 PM, jp charras wrote:
>
>> Le 10/01/2014 18:35, Maciej Sumiński a écrit :
>>
>>>
>>> On 01/09/2014 04:51 PM, jp charras wrote:
>>>
>>>> Le 09/01/2014 11:22, Tomasz Wlostowski a écrit :
>>>>
>>>>> On 01/08/2014 04:39 PM, jp charras wrote:
>>>>>
>>>>>  Tracks do not store the net name but just the net code, because they
>>>>>>
>>>>> are
>>>
>>>> expected to be connected to pads which store this info.
>>>>>> (this is the reason tracks and vias not connected to a pad lose their
>>>>>> net after loading a board, or reading a netlist)
>>>>>> Therefore, after loading a board, or reading a netlist, the track net
>>>>>> code should be initialized, but you have to store this net name in
>>>>>>
>>>>> pads.
>>>
>>>> (Of course, one can use an other way to store net names, and an other
>>>>>> way to calculate net codes)
>>>>>>
>>>>>
>>>>> Hi Jean-Pierre,
>>>>>
>>>>> I see another point in modifying the net assignment mechanism. If we
>>>>> allow tracks/vias to retain net names and propagate them from the pads
>>>>> only when the schematic netlist has changed (not every time the board
>>>>> is
>>>>> loaded), it would also fix the infamous zone stitching issue...
>>>>>
>>>>> Regards,
>>>>> Tom
>>>>>
>>>>>
>>>>>
>>>> Stitching vias and generally speaking not connected (to a pad) items
>>>> (stitching vias, usual vias and tracks) create an other problem than
>>>> retaining the net name.
>>>>
>>>> Retaining the net name of items not connected to a pad (or a zone) items
>>>> is easy to fix (I already received a patch to do that).
>>>>
>>>> But the major issue is:
>>>> if the net names are retained in not connected (to a pad) items, all
>>>> track ends and vias should be included in the ratsnest generation.
>>>> Otherwise, we will have not connected vias and/or not connected copper
>>>> zone areas (floating copper islands).
>>>> This is the only one reason stitching vias do not exist in Pcbnew.
>>>>
>>>> Therefore fixing stitching vias issue is:
>>>> 1 - finish and validate (this is the more important step toward
>>>> stitching vias) the new ratsnest algorithm which takes in account
>>>> pad+vias+track ends: mainly for very complex boards, see if it is fast
>>>> enough.
>>>>
>>>
>>> This is done by the ratsnest algorithm we added for the GAL (it is
>>> currently available in the testing branch). I have to admit that it
>>> probably is slower, but it is hard to keep the performance when amount
>>> of data for computation increases. The toughest test case I have by hand
>>> is the board that I recommended for testing the GAL
>>> (http://www.ohwr.org/attachments/download/2187/wrs.kicad_pcb), when you
>>>
>>> drag the biggest IC in the middle, as it contains the greatest number of
>>> nets connected. After being dropped you may observe a freeze for a short
>>> time, it is the ratsnest algorithm going - we have to decide if it is
>>> acceptable.
>>>
>>
>> wrs.kicad_pcb is a decent board for tests.
>>
>> The GAL ratsnest shown when moving a large footprint is very fast, no
>> problem.
>> (I tested also an other large board, and the ratsnest is also fast)
>>
>>
>>>  The current ratsnest algorithm is very fast for 6000 pads (50 ms on my
>>>> computer).
>>>> What happen for 10x to 20x more (roughly 6000 pads + 30000 tracks (2
>>>> point) and 3000 vias for instance)
>>>> 2 - after this, Retaining the net name of items not connected.
>>>> And be sure the calculation time to know if 2 items are connected by a
>>>> zone area is fast. Currently, this is 90% of calculation time.
>>>> Because stitching vias will create a *lot* of items connected by zones,
>>>> the calculation time in a very important criteria.
>>>>
>>>
>>> We take it into account during the ratsnest calculation. I agree, it
>>> takes the biggest amount of time, but still on a decent hardware is
>>> acceptable (at least in my opinion, I would like to know other views).
>>>
>>
>> The current GAL ratsnest calculation is fast.
>> Just keep in mind this is to find connections by copper areas which are
>> time consuming.
>>
>> I do not know if you are using my code for this, or a new code you wrote.
>>
>> If it is my code, I am using an usual algorithm to determine if a via,
>> pad or track end is inside a copper polygon.
>> I am thinking it could be optimized to be faster (for instance
>> considering the fact most of large copper polygon areas are built mainly
>> from very small segments, and have very few long lines.)
>>
>>
>>>  3 - add tools to change items net names, when a net name has changed in
>>>> schematic (for instance AGND changed to GND) (easy, obviously, but
>>>>
>>> needed)
>>>
>>> I think this could be handled easily if net names were kept in
>>> NETINFO_ITEM and D_PAD stored only net code or a pointer to the
>>> appropriate data.
>>>
>>
>> This is certainly easy, but must be done...
>>
>>
>>>  I know the ratsnest need to be rebuild only for the modified net (this
>>>> is also currently the case).
>>>> But the full ratsnet need to be fully rebuild, for instance when
>>>> existing copper zones are modified (when creating/moving a via, for
>>>> instance).
>>>> This is frequently the case, for complex boards.
>>>>
>>>
>>> Until now, when I was not aware of the fact that net codes are a subject
>>> to change - I indexed all items by their net codes and if anything was
>>> modified, I checked its netcode and recalculated this. This also applies
>>> to zones, vias and tracks. This is one of reasons why I wanted to keep
>>> net codes constant during a single run time.
>>>
>>
>> Net codes are subject to change only after reading a netlist.
>> Adding new net name is not allowed in pad edit dialog, and there is no
>> reason to add a new net name in a board, outside the schematic.
>>
>>
>>>  In Altium, you need to deactivate (shelve) copper polygons to be able to
>>>> work on you boards when the calculation time is too long...
>>>>
>>>
>>> I did not think of this, but actually it is a good hint to reduce
>>> computation time if user wants to do so.
>>>
>>
>> It is a good hint only for calculation time.
>> When you deactivate a copper pour, (this is *exactly* like when you
>> remove the zone filling in Pcbnew) the corresponding ratnest is no more
>> usable (you do not know anymore what is actually connected, and what do
>> you connect), and this is very bad for the user.
>> Power planes and split planes are other (poor) tricks to try to reduce
>> the calculation time.
>> But from my point of view, planes are poor features, because they are
>> not (by far) as good as true polygons.
>> The idea behind these planes is just to forbid tracks on these planes to
>> avoid connection calculations (hard to call it "a good idea": in the
>> better case this is just an idea).
>>
>>  I already have the first changes proposal. As they are related to the
>>> KiCad's core, it is very important to me if you could assess if they are
>>> suitable to commit before I move on. If you have some spare time, please
>>> have a look at the lp:~cern-kicad/kicad/netnames branch.
>>> If in your opinion they do not break anything, the next step I wanted to
>>> do is to remove m_Netname/m_ShortNetname fields, move
>>> GetNetname()/GetShortNetname() to BOARD_CONNECTED_ITEM and make them use
>>> net names stored in NETINFO_ITEMs.
>>>
>>
>> I am thinking it should break nothing.
>> But do not forget to keep a trace of the origin of net names: those
>> which are in netlist (in schematic) and those from existing items not
>> connected to a pad (currently, only the zones, but could be also not
>> connected vias and track segments) which have net names not found in
>> netlist.
>> We need to display a DRC error, and to be able to change the non
>> existent net names, or to delete corresponding items.
>>
>>
>>> Regards,
>>> Orson
>>>
>>>
>> Thanks for you work.
>>
>>
>
> _______________________________________________
> Mailing list: https://launchpad.net/~kicad-developers
> Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx
> Unsubscribe : https://launchpad.net/~kicad-developers
> More help   : https://help.launchpad.net/ListHelp
>

=== modified file 'pcbnew/CMakeLists.txt'
--- pcbnew/CMakeLists.txt	2014-01-07 20:41:32 +0000
+++ pcbnew/CMakeLists.txt	2014-01-30 18:20:12 +0000
@@ -1,6 +1,8 @@
 
 set( MAKE_LINK_MAPS false )
 
+set( CMAKE_CXX_FLAGS "-fopenmp" )
+
 add_definitions( -DPCBNEW )
 add_subdirectory(router)
 

=== modified file 'pcbnew/ratsnest_data.cpp'
--- pcbnew/ratsnest_data.cpp	2014-01-27 10:42:47 +0000
+++ pcbnew/ratsnest_data.cpp	2014-01-31 15:04:59 +0000
@@ -27,6 +27,8 @@
  * @brief Class that computes missing connections on a PCB.
  */
 
+#include <omp.h>
+
 #include <ratsnest_data.h>
 
 #include <class_board.h>
@@ -829,12 +831,31 @@
 {
     if( aNet < 0 )              // Recompute everything
     {
-        // Start with net number 1, as 0 stand for not connected
-        for( unsigned int i = 1; i < m_board->GetNetCount(); ++i )
-        {
-            if( m_nets[i].IsDirty() )
-                updateNet( i );
-        }
+		timespec ts1;
+		clock_gettime(CLOCK_REALTIME, &ts1); // Works on Linux
+		
+		unsigned int tid, i, chunk, netCount;
+		netCount = m_board->GetNetCount();
+		chunk = 1;
+		
+		#pragma omp parallel shared(chunk, netCount) private(i, tid)
+		{
+			tid = omp_get_thread_num();
+			#pragma omp for schedule(guided, chunk)
+			// Start with net number 1, as 0 stand for not connected
+			for( i = 1; i < netCount; ++i )
+			{
+				if( m_nets[i].IsDirty() )
+					updateNet( i );
+			}
+		
+		}  /* end of parallel section */
+
+		
+		timespec ts2;
+		clock_gettime(CLOCK_REALTIME, &ts2); // Works on Linux
+		
+		std::cout << "ratsnest computation time:" << (uint64_t)ts2.tv_sec * 1000000LL + (uint64_t)ts2.tv_nsec / 1000LL - (uint64_t)ts1.tv_sec * 1000000LL - (uint64_t)ts1.tv_nsec / 1000LL << std::endl;
     }
     else if( aNet > 0 )         // Recompute only specific net
     {