Subscribe to:
Post Comments (Atom)
This is an accompanying blog for the www.1024cores.net site about lockfree/waitfree synchronization algorithms and data structures, scalability-oriented architecture, multicore design patterns, high-performance computing, threading technologies and libraries, message-passing systems and related topics.
FYI http://www.kernel.org/doc/man-pages/online/pages/man2/getcpu.2.html
ReplyDeleteVERSIONS
getcpu() was added in kernel 2.6.19 for x86_64 and i386.
And the code to use it since the glibc doesn't export it is:
ReplyDelete/* This code is in the public domain */
#define _GNU_SOURCE
#include
#include
#include
struct getcpu_cache {
unsigned long blob[128 / sizeof(long)];
};
static long (*vgetcpu)(unsigned *cpu, unsigned *node, struct getcpu_cache *tcache);
static int init_vgetcpu(void)
{
void *vdso;
dlerror();
vdso = dlopen("linux-vdso.so.1", RTLD_LAZY);
if (vdso == NULL)
return -1;
vgetcpu = dlsym(vdso, "__vdso_getcpu");
dlclose(vdso);
return vgetcpu == NULL ? -1 : 0;
}
int main(void)
{
unsigned cpu, node;
struct getcpu_cache cache;
if (init_vgetcpu() < 0) {
fprintf(stderr, "Unable to locate vgetcpu: %s", dlerror());
return -1;
}
if (vgetcpu(&cpu, &node, &cache) < 0) {
perror("vgetcpu");
return -1;
}
printf("cpu:%d node:%d\n", cpu, node);
return 0;
}
and using it gives:
$ repeat 10 ./vgetcpu
cpu:0 node:0
cpu:1 node:0
cpu:0 node:0
cpu:1 node:0
cpu:0 node:0
cpu:1 node:0
cpu:1 node:0
cpu:0 node:0
cpu:1 node:0
cpu:1 node:0
(this is a core2 duo, I suppose that node is != 0 when this is a hardware thread but I don't have access to HT machines right now so somebody could probably confirm that)
Which seems to only work on X64, I must reckon I've no idea how vdso works on i386 (but who cares anyway ;p)
ReplyDeleteand I'm wrong, glibc returns it through sched_getcpu... "woopsie" ;)
ReplyDeletegetcpu is still rather heavy-weight compared to a direct call to rdtscp, vsyscall is definitely cheap in some cases but it isn't free. Per-processor distribution is nice, but sometimes you may simply want cache line distribution in which case you can use a simple subscribe/unsubscribe interface (which will also at least help alleviate some hotspot pains).
ReplyDeleteFor example,
pid = subscribe(data_structure);
operation(pid, data_structure);
...
...
unsubscribe(data_structure, pid);
where pid may be a map to a unique cache line. Additionally, if CPU migration is common and you're working with relatively small data sets then locality benefits may not exceed the cost of cache line invalidation.
@MadCoder Thanks for your suggestions. sched_getcpu() is not quite vgetcpu(). It seems that sched_getcpu() initially was a slow syscall, but I see that there is a constant progress going on:
ReplyDeletehttp://kerneltrap.org/mailarchive/linux-kernel/2008/9/23/3387414
I gave sched_getcpu() one more try, and it seems that now it's quite fast (potentially implemented with the same SIDT or LSL).
I will update the article with this and other aspects.
@sbahra
ReplyDeleteIt seems that sched_getcpu() is rather fast nowadays:
http://kerneltrap.org/mailarchive/linux-kernel/2008/9/23/3387414
Indeed, there is not reason why it can't be reimplemented with SIDT/LSL (which a cheaper that RDTSCP because there are not serializing instructions).
> but sometimes you may simply want cache line distribution
Well, actually I implied that it's a baseline, and what a lot of people are able to do. So it's vice versa :)
Per-thread subscription/unsubscription/handoff is usually leads to quite complex implementations.
> if CPU migration is common
I think then nothing will help you :)
I've updated the article with sched_getcpu(), LSL, and added clear indication that "remember in user-space it's no more than an optimization - a thread can be rescheduled to another CPU straight after it has obtained the number".
ReplyDeleteMy point was regarding overheads associated with VDSO (and DSO in general) on large multi-processor machines (where topology is not a simple 1-hop network) and not so much the specific implementation of getcpu. vgetcpu has been in Linux since 2.6.24 and sched_getcpu is implemented in terms of vgetcpu. However even on smaller multi-processor systems, getcpu is simply is not an option since sched_getcpu may still be implemented in terms of a full system call (RHEL5 is still a standard).
ReplyDeleteSubscribe/unsubscribe can provide a guarantee of cache line ownership everywhere while processor ID cannot do this in user-space if hard processor affinity is not used. You can collide very easily. In kernel-space, as you point out the ownership can be guaranteed. For memory-intensive user-space applications if the actual topology is an important factor then it is possible to set hard affinity (on Linux, see sched_setaffinity, simple interface example for RR distribution in http://codepad.org/IKLC2YkE) but this isn't suitable for applications that include a fair bit of thread deactivation and/or thread migration.
The additional complexity is totally negligible considering the attractive guarantees it can provide (in an operating system agnostic manner) if subscribe/unsubscribe frequency is low.
Note, also, you can also use TLS to implement a similar technique but abstract away the ID from the interface and all these may be coupled with the nice guarantee on some operating systems with first-touch allocation policies for NUMA (providing essentially the same benefits as using getcpu, but again, in a portable manner).
ReplyDelete@sbahra What you are saying makes perfect sense.
ReplyDeleteHowever, engineering is always about choice and trade-offs. So I just want to show alternatives and describe their trade-offs.
By the way, here is a draft of a new article "Distributed Reader-Writer Mutex" (it's not yet officially published, but almost done):
http://www.1024cores.net/home/lock-free-algorithms/reader-writer-problem/distributed-reader-writer-mutex
It shows how to build a very simple rw mutex, which still shows very good scalability.
I've done the same with per-thread approach, and I can say that the implementation is *significantly* more complicated. The problem is with synchronization between arriving/departing threads and writers, and between departing threads and mutex destruction. And by the way, it's not that easy to catch thread completion event under Windows.
vgetcpu is a vsyscall on recent linuces, and its implementation is fast and uses RDTSCP or a per-cpu variable:
ReplyDeletehttp://www.cs.fsu.edu/~baker/devices/lxr/http/source/linux/arch/x86/vdso/vgetcpu.c
Thanks for the info! Nice to hear!
ReplyDeleteNow I'm crossing my fingers for SYS_membarrier.
Hello Dmitry,
ReplyDeleteThank you for the ideas in the paper! I gave those three approaches (RDTSCP, CPUID, SIDT) a try in my microbenchmark (parallel_for over a team of 16 threads with 1 mill of tasks of (1) get_cpu_num(); (2) read a buffer of a predefined size from a memory pool and compute a check sum for the buffer (xor ints). Turns out reading from 0x7FFE0000 does not work on Windows 7. Using NtQuerySystemTime works just as good, but the return value is in 100 ns intervals, so simple != comparison in amortization function needs to be modified too.
Performance of the different approaches were as you'd expect (or as you predicted), which is SIDT is the fastest, then amortized RDTSCP, and then CPUID is the slowest one. Curious thing however is that caching latest proc_num (and apic or idt alongside of it) in TLS makes the code slower really. In my case search among 16 values (registered apics or idts for all the logical CPUs I got) worked 5% faster than the cached version of the same code.
Another finding - if you use GetSystemTimeAsFileTime instead of NtQuerySystemTime on Windows 7, it does the following under the covers:
ReplyDeletemov edx,dword ptr [7FFE0018h]
mov r8d,dword ptr [7FFE0014h]
mov eax,dword ptr [7FFE001Ch]
so, I guess "accessing the address" functionality is still there, only the address has changed a little bit.
Hi Anton,
ReplyDeleteThanks for the info!
>Turns out reading from 0x7FFE0000 does not work on...
Of course it is a dirty hack, and production code should include a dynamic check for known OS versions with a fall-back to fair GetTickCount() call.
I guess that you are working on a relatively modern version of Windows, so it would be interesting to see numbers for GetCurrentProcessorNumber().
>Curious thing however is that caching latest proc_num (and apic or idt alongside of it) in TLS makes the code slower...
Hummm... That is *not* as I would expect... Do you implement TLS with __declspec(thread)? Do you prevent several accesses to TLS?
jiain0830
ReplyDeleteair jordan 11
fitflops clearance
polo pas cher
cheap uggs
ralph lauren femme
tiffany jewellery
michael kors handbags outlet
longchamp pliage
ugg outlet
polo ralph lauren
canada goose outlet store
michael kors outlet online
cartier watches
uggs outlet
hollister canada
air jordan 13
nike outlet
versace sunglasses
coach outlet clearance
oakley sunglasses sale
longchamp outlet
swarovski outlet
tory burch outlet online
true religion canada
oakley sunglasses
true religion jeans sale
mulberry bags
air max 90
nba jerseys
ralph lauren polo
amazing content
ReplyDeleteRouterlogin
Routerlogin Net
Your initial step ought to be to discover the best rate of payday credit on offer. Whichever payday credit organization you may pick you should comprehend what will be the settled sum that you will owe after finishing your payday advance. Visit here Payday Loans Chicago
ReplyDeleteInteresting and yet informative post.. https://games.lol/racing/
ReplyDeleteGet help from professional coursework writer in UK to ease your writing tasks if you are struggling hard. We are the only online coursework writing service that caters to your every need. We are the finest British online coursework help agency to help students for almost a decade now. Coursework Help & Writing Service from Trusted Coursework Helpers.We always keep ourselves a step further from rest
ReplyDeleteI have gone through your content and I found it more relevant to what I was looking for! I really appreciate the way you have written this content including various information. However, this is to inform you about My Assignment Help Oz who provides the nonstop AutoCAD assignment help services to students who are studying at university. It offers round the clock AutoCAD assignment services with the help of subject matter experts who have at least five years of experience in the field of academic help. I am an AutoCAD assignment writer working at My Assignment Help Oz. At this company, we are bound to deliver the best AutoCAD assignment help in Australia and the rest of the countries. If you are also a student of engineering and willing to get in touch with engineering assignment help experts, just feel free to reach us immediately.
ReplyDeleteThanks for sharing this information. I have shared this link with other keep posting such information to provide best in class law assignment help online at very affordable prices.
ReplyDeleteCourse Mentor
Assignment help
Homework Help
Coursework Help
Become Mentors
how to be a mentor
how to become a mentor
Assignment help
find a mentor
how to get a mentor
how to find a mentor
Coursework Help
Coursework Writing Service
coursework writing help
Homework Help
Help With Homework
Homework Help Service
I loved the article, keep updating interesting articles. I will be a regular reader I am offering assignment help to students over the globe at a low price.
ReplyDeleteAssignment help Australia
Australian Assignment Help
Assignment writing service Australia
Online assignment help australia
Assignment Help Brisbane
Assignment help Sydney
Assignment Help Adelaide
Assignment Help Perth
Assignment Help Melbourne
Assignment Help Canbera
Essay Writing Service australia
Nursing Assignment Help Australia
University Assignment Help Australia
Write My Essay Australia
Cheap Essay Writing Service Australia
Accounting Assignment Help Australia
Many of the people are depressed about the problems of essay writing. Well, don’t worry about that because we are providing this service at a very reasonable price.
ReplyDeletedm beginners
dm beginner
digital marketing for website
digital marketing for beginner
digital marketing beginner
learn digital marketing
learn digital marketing free online
learn digital marketing free
learn seo
how to learn affiliate marketing
dm beginners
dm beginner
digital marketing for website
digital marketing for beginner
digital marketing beginner
learn digital marketing
learn digital marketing free online
learn digital marketing free
learn seo
how to learn affiliate marketing
I loved the article, keep updating interesting articles. I will be a regular reader I am offering assignment help to students over the globe at a low price.
ReplyDeleteEssay writing
Essay Writer
seo writing service
Essay writing service
Essay writing help
Write My Essay
hire seo writer
hire writer
Write my essay cheap
hire article writer
I found this one pretty fascinating and it should go into my collection. Very good work! I am Impressed. We appreciate that please keep writing more content. We are the assignment helper, we provide services all over the globe. We are best in these:- services
ReplyDeleteEcommerce CMS
Web Development Tools
Social bookmarking sites
Benefits Of Social Media Marketing
Thanks for sharing this information. I have shared this link with other keep posting such information to provide best in class law assignment help online at very affordable prices.
ReplyDeleteJava Assignment Help
"Java Homework Help
"
the-best-benefits-of-getting-java-assignment-help
How to Solve Java Programming Problems in Assignment?
how-to-find-best-programming-assignment-help-service?
how-you-can-get-c-programming-help-from-experts
how-to-make-assignment-within-a-moment
how-you-can-get-c-programming-help-from-experts?
I loved the article, keep updating interesting articles. I will be a regular reader. I am offering assignment help to students over the globe at a low price.
ReplyDeleteHow to Solve Programming Problems in Assignment
How to Hire someone to do my Statistics Homework for Me?
Highest Paying Programming Languages
big data technology
why you need to learn programming
Computer Science Homework and Assignment Help
Know How to make an Effective Python Programming Assignment
I found this one pretty fascinating and it should go into my collection. Very good work! I am Impressed. We appreciate that please keep writing more content. We are the assignment helper, we provide services all over the globe. We are best in these:- services
ReplyDeleteBest Assignment Help
What is the Importance of Statistics?
What is the best way to learn java?
What is the best way to learn Python?
What is computer science?
How to write an essay plan?
If you love playing card games, Playrummy.com provide you rummy online here! Join us now and play rummy games to win real cash.Play Online Rummy Card Games on India’s Largest Rummy Website. 100% Safe & Sure - Download the rummy app now!
ReplyDeleteThanks for sharing this information. It's really helpful for me. Want to hire an assignment writer in the USA then visit studentsassignmenthelp.com that offer the best assignment help USA services to the students.
ReplyDeleteGreat Article
ReplyDeleteNetwork Security Projects for CSE
JavaScript Training in Chennai
Project Centers in Chennai
JavaScript Training in Chennai
If you looking for the best game online click now!
ReplyDeleteClick!!>> goldenslot
Click!!>> golden slot
Click!!>> โกลเด้นสล็อต
Click!!>> สล็อตออนไลน์
Click!!>> สล็อต
Click!!>> เกมสล็อต
I am not much into reading, but somehow I got to read nice information on your site. carpet cleaning
ReplyDeleteThis article totally answered my question! Nice shower remodel
ReplyDeleteเกมออนไลน์ แจกเครดิตฟรี slot online คลิกเลย
ReplyDeletehttps://www.slotxd.com/jokergaming123
It's good for me to read this article that is about Per-processor Data. It will help me to write my assignment that is about per processor data. Custom Dissertation writing services
ReplyDelete
ReplyDeleteเล่นเกม สล็อตออนไลน์ joker123ฟรีเครดิต slot online ฟรีเครดิต
https://www.slotxd.com/jokergaming123
ดูหนังออนไลน์ สนุกๆ มากมาย ระดับ HD เรื่ิอง The App รักเสมือน (2019) [ บรรยายไทย ]
ReplyDeletePlayRummy introduces Online Rummy to the Indian market. You can learn how to play rummy card games very easily by watching videos of rummy, reading online rummy rules. Download rummy game app for FREE on your Android & IOS device for fast, secure & seamless app experience of rummy games on your mobile and enjoy favorite points anytime, anywhere.
ReplyDeleteดูได้เลยหนังออไนลน์ หนังใหม่ Delirium ลวงหลอนซ่อนผวา(2018) ดูฟรีกับเว็บดูหนังออนไลน์ที่นี่
ReplyDeletehttps://www.doonung1234.com/
เล่นเลยที่นี่ เกมยิงปลา สล็อตออนไลน์ เล่นสล็อต slotxo ฟรีเครดิต ได้เงินจริง เล่นเลยที่นี่ สนใจคลิกเลย
ReplyDeletehttps://www.slotxd.com/slotxo
หลักการเล่นสล็อตออนไลน์ ต่างจากการเล่นเกมอื่นอย่างไร
ReplyDeleteสนใจเข้าดูรายละเอียดได้ที่ >> หลักการเล่นสล็อต
ReplyDeleteเล่นเกมแล้วได้เงิน ได้ง่ายๆ ฟรีเครดิต สล็อตออนไลน์ เล่นสล็อต pgslot เครดิตฟรี ไม่มีโกง คลิกเลยที่นี่
https://www.slot2xl.com/
ทริคสล็อต - กำหนดเงินการเล่นสล็อตออนไลน์ให้เหมาะสมที่ SLOTKKK
ReplyDeleteอีกหนึ่งวิธีที่จะทำให้คุณรวยวจากการเล่นสล็อตมากที่สุดนั่นก็คือกำหนดเงินลงทุนและจำนวนเงินในการวางเดิมพันให้เหมาะสมที่สุดในเกมนั้นๆซึ่งถ้าคุณลงทุนน้อยแน่นอนว่าความเสี่ยงมันน้อยกว่าแต่เงินที่ได้กำไรมาก็คงดูน้อยเช่นกันแต่ไม่ใช่กับเว็บไซต์ SLOTKKK ที่เป็นเว็บที่จ่ายโบนัสให้คุณได้คุ้มค่ามากที่สุดแม้ลงทุนน้อย แต่ถ้าคุณลงทุนเยอะแน่นอนความเสี่ยงก็คงสูงไม่คุ้มค่าถ้าเสียแต่ถ้าคุณถูกแจ็คพอตขึ้นมาก็คงรวยข้ามคืนกันเลยทีเดียวนี่คือเหตุผลที่คุณต้องกำหนดเงินวางเดิมพันให้ดีและควรเล่นกับเราเท่านั้น
อ่านทริคเกมสล็อตอื่นๆ
I love to make my startup with a big thank to the author for this wonderfully helpful blog.
ReplyDeleteMy site : saking789
slotxo Miami slot ในเกมนี้ที่เน้นความมีสีสันของบรรยากาศชายหาดในไมอามี่ โดยมาในรูปแบบ 25 ไลน์ ซึ่งแต่ละเพย์ไลน์ก็จะมีรูปแบบการจ่ายเงินที่ต่างกันออกไป ความพิเศษของเกมนี้ที่ออกแบบสวยงามและเสียงดนตรีประกอบรู้สึกผ่อนคลายอย่างมาก ทั้งนี้ในการเล่นเกมที่จะมีการลุ้นฟรีเกมที่มีโอกาสค่อนข้างสูง เพราะคุณจะเล่นเกมที่ลุ้นเงินรางวัลได้สูงขึ้น ซึ่งในเกมนี้มีให้คุณได้ลุ้นสูงสุด 50 ครั้ง ถือว่าคุ้มค่ามาก ทั้งนี้การเลือกใช้สัญลักษณ์ต่าง ๆ ในเกมที่เกี่ยวกับบรรยากาศในชายหาดทะเลทั้งกระดานโต้คลื่น ต้นมะพร้าว
ReplyDeleteเกมสล็อตออนไลน์ยอดนิยม เกมสล็อตออนไลน์ SLOTXO
ReplyDeleteมีเกมให้เลือกเล่นหลากหลายแบบ มากกว่าร้อยเกม
พร้อมกับโปรโมชั่นสล็อตเครดิตฟรี ให้ทั้งยูสใหม่และเก่า !!
สามารถเลือกรับโปรโมชั่นและเข้าเล่นได้ที่ www.slotkkk.com
เล่น slotxo กราฟฟิกสวยงาม ความสะดวกตลอดการใช้งานที่จะทำให้การเล่นพนันของคุณมีตัวเลือกที่น่าสนใจมากกว่าการเดิมพันทั่วไป
ReplyDeleteIt is important for business management assignment help seekers to find the best Business Management Writing Services from a reputable business management paper writing service provider for their custom business management essay services.
ReplyDeleteLooking for assistance services that are too affordable? Your search is now over!
ReplyDeleteSample assignment is ready to provide you with the best assignment help in Australia .
our dedicated team of Ph.D. Scholars put their heart and soul into delivering impeccable high-quality material.
sample assignment also provides Assignment Help online to students from various universities at low prices.
Students who are looking for my assignment can contact us. our highly
experienced writers are available 24x7 to guide students for any academic assistance.
เล่นเกมแล้วได้เงิน สล็อตออนไลน์ slotxo เล่นง่ายๆ เล่นสล็อต ฟรีเครดิต slotxo
ReplyDeleteได้เงินจริง เล่นเลยที่นี่ คลิกเลย เกมยิงปลา อย่าพลาดมาลุ้นกันเลย slotxo
https://www.slot4u.com
Thank you for the ideas in the paper! I gave those three approaches.
ReplyDeleteufabet
There is an industry which combines men from countries of high income with women from the poorest parts of Asia, Latin America and the former Soviet Union. Some men are willing to spend ten thousand dollars to wed a woman they know scarcely, and those women continue to concentrate on fast emigration and migration at any expense. I advice you to find the site of the best ukrainian brides. Thanks for the attention.
ReplyDeleteThanks for share your information. Your blog has been really great. I learned a lot from here. I hope you will give us such more awesome blogs.
ReplyDelete3Movierulz
Writing services online abound. You can choose from freelance writing services for fiction, creative non-fiction or non-fiction. You can purchase the writing services of the freelance writers directly or visit the site of a writing services provider that contracts out your writing needs. Best Dissertation Writing Services UK
ReplyDeleteThanks! Its a beautiful updates and nice time visiting your blog. I sincerely appreciate your effort in putting on this article. Thanks once again for sharing. visit here fubk cut off mark for biology
ReplyDeleteAssignmenthelped provides engineering homework assistance to assist you in swiftly improving your marks. Get the best Engineering-Assignment-Help from the professionals you've been looking for. We can assist you regardless of your engineering major: electrical, dental, chemistry, physics, chemistry, psychology etc.
ReplyDelete
ReplyDeletethank you. สล็อต
สล็อตออนไลน์
I'm following you up. Its such a sensitive article and well manners write-up. I really you for sharing. I am wishing you a great success writings. Check here download pdf format data processing past questions and answers
ReplyDeletethank you สล็อตออนไลน์
ReplyDeleteสล็อต XO
This comment has been removed by the author.
ReplyDeleteGood article for everyone , พร้อมเปย์ทุกยูสเซอร์กับเกมฮิตพีจีสล็อตออนไลน์
ReplyDeleteพีจีสล็อต
This comment has been removed by the author.
ReplyDelete
ReplyDeleteNice Article and I appreciate your thought and views. This is really great work. Thank you for sharing such a useful information here on the blog. If you need any support for QuickBooks desktop error 6189 816 then get immediate help from our QuickBooks Experts.
Nice post. I was continuously checking this blog and I am inspired ! Extremely helpful info specially the ultimate part
ReplyDeleteI take care of such information a lot. For a very long time, I was looking for this specific information.
Please, Visit here : QuickBooks Payroll Error PS036
Thank you and best of luck. |