Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Determinism of parallel algorithms

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Determinism of parallel algorithms


Chronological Thread 
  • From: Niklas Hambüchen <>
  • To:
  • Subject: Re: [cgal-discuss] Determinism of parallel algorithms
  • Date: Sun, 31 Jul 2022 23:16:54 +0200
  • Authentication-results: mail3-smtp-sop.national.inria.fr; spf=None ; spf=Pass ; spf=Pass
  • Ironport-data: A9a23:kNaqk6ObhCq9EjDvrR0mkMFynXyQoLVcMsEvi/4bfWQNrUp20GcFx zQbXmuHP6qMZjf2LdpzYYWw8UpSv8TQzNdmSnM5pCpnJ55ogZqcVI7Bdi8cHAvLc5adFBo/h yk6QoOdRCzhZiaE/n9BCpC48T8kk/vgqoPUUIYoAAgoLeNfYHpn2EkLd9IR2NYy24DmWFrV4 LsenuWGULOb824sWo4rw/nbwP9flKyaVOQw4zTSzdgS1LPvvyF94KA3fcldHFOkKmVgJdNWc s6YpF2PEsw1yD92Yj+tuu6TnkTn2dc+NyDW4pZdc/DKbhSvOkXe345jXMfwZ3u7hB3OteJR9 edKrKWwYi0APfTwhr4jaClhRnQW0a1uoNcrIFC6uM2XiUvGKT3pzp2CDmlvZNNeoL4tRzgep bpJeFjhbTjb7w6y6LeyS+1EgMR5aszmVG8akis4kGuIVah2KXzFa4+b4NpE0WsKut1tTK3Gb e8YbmQzbRuVNnWjPX9MUc9hx7zz7pXlSBVTp1uR4KY2+GPO1xdZy6noKNOTe9qQRMwTkFzwm 47d12HwAxVcMtzFjz+Imp6xugPRtWTRaqIvJrqhz/5BqnSQn1ANUiMtZWLu9JFVlXWCc95YL kUV/A8noq4z6FGnQ7HBs/uQ8CfsUvk0C4A4LgEq1O2e4veNuVfIXQDoWhYQNI1/7KfaUBRwj gfhoj//OdB4mJG4IU9xG5+RpDK2fy4VdykHaEforDfpAfG4+OnfbTqWH76P9ZJZafWsQlnNL 8ii9nRWulnqpZdjOmXS1Qmvb8iQjpbIVBUpwQ7cQ3io6Ah0DKb8OdH5swmBt6wdcNbCJrVkg JTis5jHhAzpJcHX/BFhvM1SR9lFGt7fa2eA3AQ1d3Xf32TyqyP4FWyv3N2ODBwwb5lfImSBj L77uQ5N9pleJjOta6t2ZY/5BMEgzcDd+SfNBpjpgxsnSsYZSTJrCwk1Ph7IhD68yxR1+Uz9U L/CGfuR4b8hIfwP5FKLqy01iNfHHwgymjHeQ47V1ROi3ebMbXKZU+lXNlvUKOU0tfvWrALQ+ tdZFs2L1xQGCrekP3KHq9VKIABYN2U/CLD3t9dTKryJLD1gFTxzEPTW274gJ9Fokv0NxOfF9 32wQGFCz1/7iSGVIAmGcC4xbrO1G5Ny9CppMSspNFeu+n4ifYf2tv1FKsBnJ+J++bU6n/BuT vQDd8GROdh1S2zKq2YHcJ3wjI1+bxD31wiACCyoPWokdJl6Sg2Vp9Lpc1e99CQKCSbr58Iyr 6f5j1HeSJsHAQJiVoDTZav3nV+2uHEcnsN0XlfJe4MJIhi3oNIxciGh3OUqJ8wsKAnYwmfI3 QihBxpF9/LGpJU48YWUiK3Y/Z2lFfByQhhTE2XBtO/kMCDb+iylwdUGVevRJWLRU2b9+aODY +RJzqimaqdaxwYQ6NNxQ+Rx0KYzx9rzvLsGnA5qK3PGMgawAbR6L3jagMRCu8WhHFOCVddah 65OxjVbBVlNEMbsEVpXIgp/KOGOvR3RsieH9uw7eS0W+wculIdrk20LV/VPtMCZBL11asUgz I/NfeYIvhenhENC3smu10hpGqflEpDEe6Mn7NcfDecHT+btJk5qOfThN8M93H1Dhxig/KXnz v94SZcuX4hh+3c=
  • Ironport-hdrordr: A9a23:2rNtvqiErnwNqOHC0mo59Ag9DXBQXtEji2hC6mlwRA09TyXqra 6TdZMgpHvJYVcqKRQdcLW7UpVoLkmwyXcY2/hzAV7mZniFhILKFu1fBOnZqAEIcheWntK1l5 0BT0EUMrLN5DZB7PrH3A==
  • Ironport-phdr: A9a23:BShLPhPruPVBZAqeHSkl6nZWBhdPi9zP1u491JMrhvp0f7i5+Ny6Z QqDv64r1gWQFtyFsbptsKn/i+jYQ2sO4JKM4jgpUadncFs7s/gQhBEqG8WfCEf2f7bAZi0+G 9leBhc+pynoeUdaF9zjaFLMv3a88SAdGgnlNQpyO+/5BpPeg9642uys9ZDfeRtEiCSgbb99M Rm7rBvdvdQKjIV/Lao81gHHqWZSdeRMwmNoK1OTnxLi6cq14ZVu7Sdete8/+sBZSan1cLg2Q rJeDDQ9LmA6/9brugXZTQuO/XQTTGMbmQdVDgff7RH6WpDxsjbmtud4xSKXM9H6QawyVD+/6 KhlVgHniSgbNzAg9mHXjsxxgLtCrB+9qRFywYDZbJiJOPdxY6jRedMXSXZEUstXSidPAJ6zb 5EXAuQCM+hXoJTzqUUArRW+BwajGOzhxyRUhnL0x6A2z/gtHR3E0QEmAtkAsG7UrNLwNKoKS e61zarIzTHZYPNNwTjz6pLHchU6rumQQb1wcdTeyU8yHA7Ci1Wfs43lPzeO2+QLs2iX8fBsV eexhGM+rQx6vzegyNs2hIbTmoIV1k7L9T9/wIstJ9C0VU51bNCkHpdNuS+XNZd7Tt8mTm9nt yg2170LtIC/cSYK1ZkpxwLTZfyHfoaH4x/vSemfLCl4iX55ZL6yhhC/+lWuxO37U8m7yldKr ixdn9nDt3ANyxzT6tWcRfdn4kih3jOP2gbO4e9HOUA5jbfXJ4Mgz7IqiJYfrVrPEjXrlEj1j 6KabEEp9+uu5u/6eLvpvIWcOJVxigzmMqQhhMi/AeMgPwgLRWeb+OC82Kfl/U35XrlGlPg2n bfBvJDbI8QUuLK5DhdI3oo+6huzFSmq3MgGkXUdMV5IexGKg5LtNlzNOPz4CO2wg1WokDdl3 fDGObjhD43ILnfZkbfhea1w60hcyAYt19xf4oxbBqkHIP3oQkDxrsDXDgclMwyoxObqEMhx2 psEWW2TGq+ZLL/SsViQ6+0zLOmDfosVtC/gJPgk/P7hkWI5mUQGfaSyxpsWaHW4Hux8LEmDY HrshM0BEWYQsQYkQuzqkg7KbTkGbHm7W+cw5yowFZm9JYbFXIGkxrKbjwmhGZgDQGFFDlmXJ lfhco8QUPcBbmrGJ8ZglhQCVeLnToJ3hkLmjxPz17cydrmcwSYfr5+2iYAdD4z7kBgz8WcxF MGByySWSHkymGoURjgw1aQ5oEpny17F37Iry+dAG4l14PVEGhw/KYaa1/ZzXtX7WwbpeNfTD lOrEZ29GT9kdtsq2JcVZlplXdCrjxTNxS2vVroclrijApxutKfRjDDqP8go83/dz+E6ikU+B MtCMWrznqlk6w3aHJLEiW2cnqeuM6IchmjI+Q9v1EKou0dVGE51WKTBBjUEY1fO6M/+/gXER qOvDrIuNk1Az9SDI+1EcI+hi1IOX/rlNNnEBgD5026tGRaFwK+NZ4v2ai0c2ivaEk0NjwEU+ z6PKwE/Ai6rp2+WAiZpEBrjZEbl8O82r33eLAd8ygiLa2Vn1+Dz/xNUzf2QRvUP364V7T87o mY8F1K80tTKTtuY8lM4IuMGOYl7uQcXkzOJ5GkfdtS6Iqtvh0ATaVFytkLqjFBsD5lY1NMtt DUsxRZzLqSR1BVAcSmZ1Nb+IO6ySCG68RaxZqrRwlyb3syR//JF7f05r33lvFvvE0dooD13l sJY1XeR/MCACQMTVbr3Uhxx8hUw9NS4KmEtoojT03NrK6y9tDTPjskoCOUSwRGlZ95DMamAG WceCuUiDtO1YKwvklmtNVcfOfxKsbUzJ4WgfueH36iiOKBhmiinhCJJ+tI13kWJ/it6AunGu vRNi/SR3w+vUTemylKs+sz6goFLYzgOE3H3kHG6QtQJPOsrLdZNWDfmKtb/3thkgp/xR3NUv EWuAV8Lwo7MG1LablDw2xFRyVVCpHWmnSWiyDkn2zotr6eZwGnP27G7LURBYDYRAjAy3RG9c dvR7ZhSRkWjYgk3mQHw4E/7w/Mev6FjNyzIRl8OeSHqLmZkW6/2t7yYYscJ5ol71EcfGOm6f 12eTabw5hUA1Ca2VW5XxTQTcTHw/JD01U8ymCeGIXB/oWCMM8R5xBP34tyGA/tclGljJmEwm XzcAV6yOMOs9NOfmsLYs+ywYGmmU4VabSjhyY7T/Dv+/2BhBgez2uyigtCyWxZvyjf1jpM5M EeA5Aa5eITg0L62dP5qblU9TkGp8NJ0Q8k9m8NzgYFYz3Eegt/9EWMvqW7oKp0b3Kv/aCFIX jsX25vO5xCj3kR/L3WPzoa/V3OHw8InacPoKm8R3ys86YhNBsL2pPRcmjBpp1OjsQ/LSf10n zNbz/t0rnsXy+0EowsiyCyBD6taRBAGe3a0zVLRv4D4/fUfbX3nabWq0Utigd2tadPK6hpRX nr0YNZqHCN96Nl+LEOZ0HD37dKsc93RYNQP8xyMxk6Z0a4PcMh3z6paw3s3agef9TU/xuU2j AJjx8S/tYmDcCB2+b6hRwVfLnvzbt8S/TfkieBfmNyX1sahBMYEeH1DUZ32QPavCD9Xu+7gM lPEFTQ9rl+dGeCZGALVuyIE5zrfVoumMX2aPixT1dJ5WByUP1BSmigRVTQ+2Jg5TEavyYayF SUxriBU7Vn+pBxWz+tuPBSqSWbTqjCjbTIsQYSeJh5bvUlSol3YOsuE4qdvDjlVq9e/+ReVJ DXRNGEqRSkZH1aJDFf5Mvyy6MncpqKGU/GmIaKGIrzG7OVaU73gLX2H1Is8uTOBZJzn1pxKC f1hnE9ODygR8yXxnjwOT2oRl3iLasPJ/X+B
  • Ironport-sdr: z0n4XuX89QTTexlH8tM9qhk+VtpTkp4cdH6xOIr3pdjqxgzjx0qqQD16fj9zXGNKAFJu/Vxi7n iZFLI377MC63dbW35bNwxR0yrwF7LKezEBYDDpsutzz47Vfmyfnu+buszBW0YfqGRIV3kEoSlX UzGwABL9IDJEBIijBW/tVBQcH0FO/mG9DmdOzfs1zMpYEcn0V0sbE28g3+KNxcc8FsViEfRpZs JASDfuRLLT06nGZ1LS0f9vljxEhLHnggMlJWdhNfn0ZKzGR8Y2A2+tB8KOGYp+TIq4jdCL3YNK Bf7WGNmtZ7JJQLh1c30HSHdN

Hey Sebastien,

thanks for your reply!
Sounds like I will indeed have to look at each implementation in detail.

For spatial sorting, there is an initial random sampling so no
seeding is used it is not deterministic, even in sequential.

I had a quick look at it:

In spatial_sort.h, CGAL seems to use `boost::rand48`'s default constructor

https://github.com/CGAL/cgal/blob/0af45fa11efee1030a00f94695107c79536533ce/Spatial_sorting/include/CGAL/spatial_sort.h#L67

which according to

https://github.com/boostorg/random/blob/1e9bfb8b3232093646df4c491e01a4f9667be783/include/boost/random/linear_congruential.hpp#L365-L366

uses the constant seed `1` so it should be deterministic in the sequential
case.

Niklas



Archive powered by MHonArc 2.6.19+.

Top of Page