Rapporteur at JavaOne 2008 from Dr. Cliff Click from Azul Systems one of the Best in the world specialist in Super-Scalable(768 and Up cores) Non-Blocking structures for Java.
Author of high-scale-lib (free lib at SourceForge) (lib has BitVector, HashTable and (FIFO-Queue in progress now)).
Dr. Cliff Click talk how by using FSM(Finite State Machine) and atomic-CAS create scalable non-locking structures.
"Classic reader/writer lock chokes w/ >100 CPUs
• Contention on single reader-count word limits scaling"
"• Lock-Free: Each CAS makes progress
• CAS success is local progress
• CAS failure means another CAS succeeded(global progress, local starvation)"
"JDK API mistake: witness turned into a boolean
• Hence failure-for-cause can not be distinguished from spurious-failure"
"Highly scalable (proven scalable to ~1000 CPUs)"
P.S. FSM model for verification maybe interesting for you, Igor?
Не знаю как на Azul'ах, но на х86 его метод не мастабируется.
ОтветитьУдалитьЭто результат твоих экспериментов? Было бы интересно почитать.
ОтветитьУдалитьИ в чем загвоздка на x86?
Централизованные модифицируемые структуры не масштабируются на х86, как ни крути. На Sun'овских CMT процессорах ситуация с этим значительно лучше. Как на Azul'ах не знаю, но подозреваю, что для таких большим машин тоже не лучшим образом.
ОтветитьУдалитьПо поводу моих экспериментов, мой хэш мап на Intel Core2Quad Q6600 показывает ту же производительность, что и хэш мап Клика на 200-процессорном Азуле.
ОтветитьУдалитьСмотри (начиная с "Azul vs. Dmitriy's hash-map"):
http://groups.google.com/group/comp.programming/browse_frm/thread/3bc9742b375c8e87
Хотя это не имеет отношения к подходу "CAS FSM", т.к. речь о read-only нагрузке (под write нагрузкой наши оба хэш мапа деградируют - насколько именно не знаю).
"Мой хэш мап" это вот это:
ОтветитьУдалитьhttp://software.intel.com/en-us/forums/intel-threading-building-blocks/topic/60494/
http://groups.google.com/group/lock-free/files