MIT’s Multicore Swarm Architecture Advances Ordered Parallelism

By John Russell

July 21, 2016

A relatively new architecture explicitly designed for parallelism – Swarm – based on work at MIT has shown promise for substantially speeding up classes of applications (graphs, for example) and decreasing the programming burden to achieve parallelism. The work, recounted in a recent paper, Unlocking Ordered Parallelism with the Swarm Architecture, bucks conventional wisdom and adopts the ‘ordered’ program execution model.

“Multicore systems are really hard to program. You have to explicitly divide the work that you’re doing into tasks, and then you need to enforce some synchronization between tasks accessing shared data. What this architecture does, essentially, is to remove all sorts of explicit synchronization, to make parallel programming much easier,” said project leader Daniel Sanchez in an account of the work on MIT’s website.

In the paper[i], the authors wrote, “First, conventional wisdom says that order constraints limit parallelism. However, we have shown that it is possible to maintain a large speculation window efficiently, so that only true data dependencies limit parallelism. Second, conventional wisdom says that speculation is wasteful, and designers should instead build nonspeculative parallel systems. However, we have shown that, for a broad class of applications, speculation unlocks abundant parallelism for moderate costs.”

MIT SWARM.1.PM

Using the SWARM architecture on a 64-core device (see above) to run a set of graph analytics, simulation, and database benchmarks, the authors report SWARM outperforms sequential implementations of these algorithms by 43 to 117 times and state-of-the-art software-only parallel algorithms by 3 to 18 times. SWARM exploits ordered parallelism with these four novel techniques:

  • Execution model based on tasks with programmer-specified time stamps that conveys order constraints to hardware.
  • Hardware task-management scheme that features speculative task creation and dispatch, drastically reducing task management overheads, and implements a large speculation window.
  • Scalable conflict-detection scheme that leverages eager versioning to, upon mispeculation, selectively abort the mispeculated task and its dependents.
  • Distributed commit protocol that allows ordered commits without serialization, supporting multiple commits per cycle with modest communication.

Applications with ordered parallelism have three key features, note the authors. First, they comprise tasks that must execute in some total or partial order. Second, tasks are not known in advance. Instead, tasks dynamically create children tasks and schedule them to run at a future time, resulting in different task creation and execution orders. Third, tasks can have data dependencies that are not known a priori.

The approach relies on speculative execution, which works because most of the order constraints are superfluous. Except for the earliest active task, Swarm assumes there are no earlier data-dependent tasks, and it executes the task speculatively. When Swarm detects a dependence has been violated, the offending task is aborted.

Order is enforced with task units that assign each dispatched task a unique virtual identifier comprised of the task’s time stamp and a unique tiebreaker. “To uncover enough parallelism, task units can dispatch any available task to cores, no matter how distant in program order. Tasks also can run even if their parent is still speculative,” note the authors.

“Swarm guarantees that tasks appear to execute in time-stamp order,” they further describe. “If multiple tasks have the same time stamp, Swarm chooses an order among them. Using time stamps decouples task creation and execution orders: software conveys new work to hardware as soon as it is discovered rather than in the order it needs to run, exposing a large amount of parallelism.”

The hybrid approach (software and hardware), say the researchers, not only achieves near-linear scalability on algorithms that are often considered sequential, but also results in “Swarm programs [that] are almost as simple as their sequential counterparts, because they do not use explicit synchronization.”

Programs leverage the Swarm execution model through an API, illustrated below (figure 2).

MIT.SWARM.2

Link to the summary paper: https://people.csail.mit.edu/mcj/papers/2016.swarm.toppicks.pdf

Sources: MIT; IEEE

[i] Unlocking Ordered Parallelism with the Swarm Architecture, Authors include Mark C. Jeffrey (MIT), Suvinay Subramanian (MIT), Cong Yan, University of Washington, Joel Emer MIT and Nvidia; Daniel Sanchez (MIT); IEEE Micro, May/June 2016.

Subscribe to HPCwire's Weekly Update!

Be the most informed person in the room! Stay ahead of the tech trends with industy updates delivered to you every week!

What’s New in HPC Research: ROBE, OpenMP Automated Scheduling, SCALSALE, & More

October 6, 2022

In this regular feature, HPCwire highlights newly published research in the high-performance computing community and related domains. From parallel programming to exascale to quantum computing, the details are here. Read more…

China Expands Quantum Computing Development Push says Report

October 6, 2022

The drumbeat around development of quantum computing continues to grow in mainstream media, as evidenced by a report in today’s Wall Street Journal (China Seeks a Quantum Leap in Computing). While timelines for practic Read more…

Intel Is Opening up Its Chip Factories to Academia

October 6, 2022

Intel is opening up its fabs for academic institutions so researchers can get their hands on physical versions of its chips, with the end goal of boosting semiconductor research and development. The effort, called the Read more…

NCSA’s Delta System Enters Full Production

October 5, 2022

In June 2020, the NSF awarded the National Center for Supercomputing Applications (NCSA) $10 million for its post-Blue Waters “Delta” supercomputer. Now, that funding has come to fruition: NCSA has announced that Del Read more…

GM, National Labs Pave the Way for Next-Gen Vehicles

October 5, 2022

For the better part of a century, General Motors (GM) was the biggest automaker in the world. Now, amid a paradigm shift toward smarter, electrified vehicles, the leading American automaker is working to meet the moment Read more…

AWS Solution Channel

Shutterstock 242193979

Last Chance to Vote – AWS for Best Use of HPC in the 2022 Readers’ Choice Awards

AWS Once Again Showcasing its Reach Across Several Areas in HPC

Ten categories feature Amazon Web Services (AWS) in the 2022 HPCwire Readers’ Choice Awards. Read more…

Microsoft/NVIDIA Solution Channel

Shutterstock 1166887495

Improving Insurance Fraud Detection using AI Running on Cloud-based GPU-Accelerated Systems

Insurance is a highly regulated industry that is evolving as the industry faces changing customer expectations, massive amounts of data, and increased regulations. A major issue facing the industry is tracking insurance fraud. Read more…

Quantum Computing Needs More Public-Private Collaboration Says QED-C

October 4, 2022

Last week the Quantum Economic Development Consortium (QED-C) released a new report – Public-Private Partnerships in Quantum Computing – that calls for increased government-commercial collaboration, broadly describes Read more…

Intel Is Opening up Its Chip Factories to Academia

October 6, 2022

Intel is opening up its fabs for academic institutions so researchers can get their hands on physical versions of its chips, with the end goal of boosting semic Read more…

GM, National Labs Pave the Way for Next-Gen Vehicles

October 5, 2022

For the better part of a century, General Motors (GM) was the biggest automaker in the world. Now, amid a paradigm shift toward smarter, electrified vehicles, t Read more…

Quantum Computing Needs More Public-Private Collaboration Says QED-C

October 4, 2022

Last week the Quantum Economic Development Consortium (QED-C) released a new report – Public-Private Partnerships in Quantum Computing – that calls for incr Read more…

How Intel Plans to Rebuild Its Manufacturing Supply Chain

September 29, 2022

Intel's engineering roots saw a revival at this week's Innovation, with attendees recalling the show’s resemblance to Intel Developer Forum, the company's ann Read more…

Intel Labs Launches Neuromorphic ‘Kapoho Point’ Board

September 28, 2022

Over the past five years, Intel has been iterating on its neuromorphic chips and systems, aiming to create devices (and software for those devices) that closely Read more…

HPE to Build 100+ Petaflops Shaheen III Supercomputer

September 27, 2022

The King Abdullah University of Science and Technology (KAUST) in Saudi Arabia has announced that HPE has won the bid to build the Shaheen III supercomputer. Sh Read more…

Intel’s New Programmable Chips Next Year to Replace Aging Products

September 27, 2022

Intel shared its latest roadmap of programmable chips, and doesn't want to dig itself into a hole by following AMD's strategy in the area.  "We're thankfully not matching their strategy," said Shannon Poulin, corporate vice president for the datacenter and AI group at Intel, in response to a question posed by HPCwire during a press briefing. The updated roadmap pieces together Intel's strategy for FPGAs... Read more…

Intel Ships Sapphire Rapids – to Its Cloud

September 27, 2022

Intel has had trouble getting its chips in the hands of customers on time, but is providing the next best thing – to try out those chips in the cloud. Delayed chips such as Sapphire Rapids server processors and Habana Gaudi 2 AI chip will be available on a platform called the Intel Developer Cloud, which was announced at the Intel Innovation event being held in San Jose, California. Read more…

Nvidia Shuts Out RISC-V Software Support for GPUs 

September 23, 2022

Nvidia is not interested in bringing software support to its GPUs for the RISC-V architecture despite being an early adopter of the open-source technology in its GPU controllers. Nvidia has no plans to add RISC-V support for CUDA, which is the proprietary GPU software platform, a company representative... Read more…

AWS Takes the Short and Long View of Quantum Computing

August 30, 2022

It is perhaps not surprising that the big cloud providers – a poor term really – have jumped into quantum computing. Amazon, Microsoft Azure, Google, and th Read more…

US Senate Passes CHIPS Act Temperature Check, but Challenges Linger

July 19, 2022

The U.S. Senate on Tuesday passed a major hurdle that will open up close to $52 billion in grants for the semiconductor industry to boost manufacturing, supply chain and research and development. U.S. senators voted 64-34 in favor of advancing the CHIPS Act, which sets the stage for the final consideration... Read more…

Chinese Startup Biren Details BR100 GPU

August 22, 2022

Amid the high-performance GPU turf tussle between AMD and Nvidia (and soon, Intel), a new, China-based player is emerging: Biren Technology, founded in 2019 and headquartered in Shanghai. At Hot Chips 34, Biren co-founder and president Lingjie Xu and Biren CTO Mike Hong took the (virtual) stage to detail the company’s inaugural product: the Biren BR100 general-purpose GPU (GPGPU). “It is my honor to present... Read more…

Tesla Bulks Up Its GPU-Powered AI Super – Is Dojo Next?

August 16, 2022

Tesla has revealed that its biggest in-house AI supercomputer – which we wrote about last year – now has a total of 7,360 A100 GPUs, a nearly 28 percent uplift from its previous total of 5,760 GPUs. That’s enough GPU oomph for a top seven spot on the Top500, although the tech company best known for its electric vehicles has not publicly benchmarked the system. If it had, it would... Read more…

AMD’s MI300 APUs to Power Exascale El Capitan Supercomputer

June 21, 2022

Additional details of the architecture of the exascale El Capitan supercomputer were disclosed today by Lawrence Livermore National Laboratory’s (LLNL) Terri Read more…

Exclusive Inside Look at First US Exascale Supercomputer

July 1, 2022

HPCwire takes you inside the Frontier datacenter at DOE's Oak Ridge National Laboratory (ORNL) in Oak Ridge, Tenn., for an interview with Frontier Project Direc Read more…

AMD Opens Up Chip Design to the Outside for Custom Future

June 15, 2022

AMD is getting personal with chips as it sets sail to make products more to the liking of its customers. The chipmaker detailed a modular chip future in which customers can mix and match non-AMD processors in a custom chip package. "We are focused on making it easier to implement chips with more flexibility," said Mark Papermaster, chief technology officer at AMD during the analyst day meeting late last week. Read more…

Leading Solution Providers

Contributors

Nvidia, Intel to Power Atos-Built MareNostrum 5 Supercomputer

June 16, 2022

The long-troubled, hotly anticipated MareNostrum 5 supercomputer finally has a vendor: Atos, which will be supplying a system that includes both Nvidia and Inte Read more…

UCIe Consortium Incorporates, Nvidia and Alibaba Round Out Board

August 2, 2022

The Universal Chiplet Interconnect Express (UCIe) consortium is moving ahead with its effort to standardize a universal interconnect at the package level. The c Read more…

Using Exascale Supercomputers to Make Clean Fusion Energy Possible

September 2, 2022

Fusion, the nuclear reaction that powers the Sun and the stars, has incredible potential as a source of safe, carbon-free and essentially limitless energy. But Read more…

Is Time Running Out for Compromise on America COMPETES/USICA Act?

June 22, 2022

You may recall that efforts proposed in 2020 to remake the National Science Foundation (Endless Frontier Act) have since expanded and morphed into two gigantic bills, the America COMPETES Act in the U.S. House of Representatives and the U.S. Innovation and Competition Act in the U.S. Senate. So far, efforts to reconcile the two pieces of legislation have snagged and recent reports... Read more…

Nvidia, Qualcomm Shine in MLPerf Inference; Intel’s Sapphire Rapids Makes an Appearance.

September 8, 2022

The steady maturation of MLCommons/MLPerf as an AI benchmarking tool was apparent in today’s release of MLPerf v2.1 Inference results. Twenty-one organization Read more…

Not Just Cash for Chips – The New Chips and Science Act Boosts NSF, DOE, NIST

August 3, 2022

After two-plus years of contentious debate, several different names, and final passage by the House (243-187) and Senate (64-33) last week, the Chips and Science Act will soon become law. Besides the $54.2 billion provided to boost US-based chip manufacturing, the act reshapes US science policy in meaningful ways. NSF’s proposed budget... Read more…

AMD Lines Up Alternate Chips as It Eyes a ‘Post-exaflops’ Future

June 10, 2022

Close to a decade ago, AMD was in turmoil. The company was playing second fiddle to Intel in PCs and datacenters, and its road to profitability hinged mostly on Read more…

RISC-V Opens the Door on 48-bit Computing

July 7, 2022

There’s a growing interest among silicon providers backing RISC-V to introduce 48-bit computing in custom chips to meet their specific requirements. The 48-bit long instructions focus is more as a middle ground between 32-bit and 64-bit, which has largely been the focus of chips and instruction sets until now. Read more…

  • arrow
  • Click Here for More Headlines
  • arrow
HPCwire