Posts Tagged ‘research’
Everything You Always Wanted to Know about Synchronization but Were Afraid to Ask
November 1, 2013 | 
Author It’s just one day before traveling to the US to present “Everything You Always Wanted to Know about Synchronization but Were Afraid to Ask” in the the 24th ACM Symposium on Operating Systems Principles (SOSP). I am really glad that I will have the opportunity to share the knowledge we collected in over a year of hard work. You can get a copy of the paper here.
This publication is about understanding the low-level details of the hardware (e.g., the cache-coherence protocol) and how they affect synchronization (and sharing of data in general) in software. If you want to better understand your hardware, to optimize your system/application, or to understand why something scales or does not scale, I believe you will be interested in reading the paper.
We also published the software we developed to perform this study as the SSYNC synchronization suite (SSYNC stands for Simple Synchronization). If the information in the paper is not sufficient for your needs, or if you have a hardware platform that is not very similar with the ones we used in the paper, then you can use the tools and libraries of SSYNC to evaluate your own platform.
SSYNC is available at http://lpd.epfl.ch/site/ssync and contains:
- ccbench: a tool for measuring the latencies of the hardware cache-coherence protocol
- libslock: a library with cross-platform implementations of various locking algorithms
- libssmp: a message passing library optimized for x86, SPARC, and Tilera platforms
- TM2C: the first software Transactional Memory for Many-Cores
I hope you will enjoy reading the paper 🙂
Posted in Computer Science | 
Tags: many-core, multi-core, research, SOSP, sycnhronization | 
No Comments »
Not P==NP for now..
Some time ago (January 19, 2011), Vladimir Romanov announced that he had found a polynomial time solution for the 3-SAT NP-Complete problem. As I mentioned on the first related post, if this was true it would immediately suggest that P==NP.. A nice article about what would be the implications of this equality can be found in Wikipedia.
The time for such a proof (or the opposite one, which is consider to be more probable) has not come yet. Yesterday, with a comment to his blog, Vladimir Romanov announced that there is a problem with the solution that need to be corrected:
Thank you for your attention to my work. You’d better suspend your investigations.
A shortcoming possibly exists in the filtration procedure which requires an amendment.Best regards,
V. R.
3-SAT polynomial time solution? If true then P==NP
Complexity classes
One of the biggest questions in the CS always was (is) if P==NP, or P!=NP.
I just read a post announcing an article called “Non-Orthodox Combinatorial Models Based on Discordant Structures” by the author V. F. Romanov (http://arxiv.org/abs/1011.3944).
According to the author:
The article presents a constructive proof of effective resolvability of 3-SAT problem, accompanied by description of a polynomial algorithm created for the named purpose.
If this statement is correct, and the algorithm really solves the 3-SAT problem in polynomial time, then P==NP (since 3-SAT is NP-complete). Although the article, in my opinion, looks too draft for such an important topic, if it will be proven correct, one of the biggest findings in CS will be unveiled.
Lets see..
FPGA as a processor?
I just read an article about some research being done on University of Glasgow. Researchers placed/programmed (more than) 1000-cores on an FPGA (about FPGA). Each core is supposed to have each own dedicated memory (it is not a technical article, so not many technical details were given). According to the article:
The researchers then used the chip to process an algorithm which is central to the MPEG movie format – used in YouTube videos – at a speed of five gigabytes per second: around 20 times faster than current top-end desktop computers.
You can read the article here.