Dangling Pointers 5 days ago

Vector Value Prediction with Element-wise Stride Compression

Vector Value Prediction with Element-wise Stride Compression Yanmeng Huang, Ling Yang, Yuanhu Cheng, Junhui Wang, Quan Deng, Junbo Tie, Yongwen Wang, Hai Zhong, and Libo Huang GLSVLSI'26 This paper makes an astute observation: the contents of vector registers are losslessly compressible. There are many hardware and architectural optimizations that can be derived from this fact. This paper presents one: prediction of vector register values. The point of value prediction is to expose more parallelism to a modern processor, so that more instructions can be executed in parallel. Much like branch prediction, value prediction speculatively breaks dependencies to allow the processor backend to process a less-constrained set of instructions. If the predicted value ends up being wrong, then the processor must throw away some work and start over. One way to implement value prediction is much like branch prediction, using the PC and branch history as the index into a table which contains a predicted value and a level of confidence that the predicted value is correct. This paper describes such a technique. SIMD instructions are an orthogonal way to expose more parallelism to a processor backend. Since value prediction and SIMD are orthogonal, why not combine them? Two reasons: The predictor must predict the values of all lanes of a vector register. If any one lane is a bad apple, it spoils the bunch. The data structures needed to make accurate vector-wide predictions would consume a lot of on-chip memory (storage would grow linearly with vector width) The core idea of this paper is illustrated in Fig. 1: Source: https://dl.acm.org/doi/full/10.1145/3787109.3815244 The left side of the figure shows raw (uncompressed) vector registers with varying element widths. The right side shows compressed versions. The gray rectangle represents the value stored in lane 0 (no compression). The orange rectangles hold the differences (i.e., strides ) between neighboring elements. The magnitude of a stride is typically small, so strides are stored with only a few bits per stride. Here is a concrete example: The key point here is that the base + strides representation consumes fewer bits than the raw representation. If the values in a particular register cannot be represented with the base + strides representation, then those values are not considered candidates for value prediction. Fig. 6 shows IPC improvements provided by vector value prediction across a set of benchmarks: Source: https://dl.acm.org/doi/full/10.1145/3787109.3815244 Dangling Pointers I didn’t see specific handling for floating point values in the paper. I wonder if a dedicated compression scheme for those types is warranted. Thanks for reading Dangling Pointers! Subscribe for free to receive new posts. The predictor must predict the values of all lanes of a vector register. If any one lane is a bad apple, it spoils the bunch. The data structures needed to make accurate vector-wide predictions would consume a lot of on-chip memory (storage would grow linearly with vector width)

Hardware Performance

▲ 0

0 views

Dangling Pointers 1 weeks ago

Modular GPU Programming with Typed Perspectives

Modular GPU Programming with Typed Perspectives Manya Bansal, Daniel Sainati, Joseph W. Cutler, Saman Amarasinghe, and Jonathan Ragan-Kelley PLDI'26 GPU programming is great, who doesn’t want to copy memory with thousands of threads? The trouble is that some operations require multiple threads to cooperate, and current GPU programming languages only have kludgy ways of expressing such cooperation. For example, see the fine print on the function from the CUB library (quoting from the paper which quotes from the CUB documentation): Computes a block-wide reduction for thread0 using the specified binary reduction functor. • The return value is undefined in threads other than thread0. • A subsequent __syncthreads() threadblock barrier should be invoked after calling this method if the collective’s temporary storage (e.g., temp_storage) is to be reused or repurposed This paper introduces the Prism language, which uses perspectives to bring some much-needed hierarchy to GPU programming Prism supports 3 coarse-grain levels of nesting: , , . indicates when code/data applies to pairs of threads. applies to a warp of threads. is used to indicate a group of 8 blocks. Grids are broader (i.e., coarser) than blocks, which are broader than threads. Also, is broader than (this only applies when the larger integer is divisible by the smaller one). Each statement is associated with a stack of perspectives, and the operator can be used to push an element on to the stack. For example: Similarly, local variables are annotated with a perspective, to indicate how they are shared among threads: Perspectives are the foundation upon which Prism builds higher level concepts and a type system that enable hierarchical parallelism to be expressed. This allows for code that is more modular and easier to reason about than the typical flat parallelism found in other languages. For example, Prism statically disallows a code operating at a broad perspective from reading the value of a variable declared with a narrow perspective (only read up is allowed). Similarly, local variables can only be written from a perspective that is the same as the variable’s perspective or broader ( write down is allowed). Fig. 22 compares various Prism implementations of a matrix multiply against , not too shabby. Source: https://dl.acm.org/doi/10.1145/3808290 Dangling Pointers The interface exposed by GPUs doesn’t natively support nested parallelism. I wonder if there is an opportunity for hardware to take advantage of hierarchically information that is available at the Prism level of abstraction. Thanks for reading Dangling Pointers! Subscribe for free to receive new posts.

Programming

▲ 0

0 views

Dangling Pointers 2 weeks ago

RNG: Flat Datacenter Networks at Scale

RNG: Flat Datacenter Networks at Scale Giacomo Bernardi, Ratul Mahajan, C. Seshadhri, Enrico Carlesso, Chinchu Merine Joseph, Saurabh Kumar, Pavan Manikonda, Luiza Popa, Randy Ram, Steven Robinson, Elizabeth Tennent arXiv This paper from Amazon describes an alternative to fat tree network topologies. In a fat tree, switches are organized into a strict set of levels (top-of-rack switches being the leaves). The tree is called fat because each switch at given level can be connected to multiple switches at a higher level. The paper describes the core problem of fat trees as capacity fungibility . Only a small set of network links are available to route traffic between any specific pair of switches. Fig. 1 compares a fat tree to an expander network (yellow circles represent top-of-rack switches): Source: https://arxiv.org/abs/2604.15261 The expander network has no visible structure, the connections are effectively random. Switches in this network use spraypoint routing to move packets to their destination. In spraypoint routing, all pairs of switches ( , ) are classified according to how packets destined for should be routed. Fig. 3 illustrates the classification scheme assuming that a packet is destined for switch : Source: https://arxiv.org/abs/2604.15261 Switches are classified as waypoint level 0 (WP 0 ) switches relative to . These switches are directly connected to . When a packet destined for arrives at a WP 0 switch, the packet is forwarded to . Switches are classified as waypoint level 1 (WP 1 ) switches relative to . These switches are not directly connected to but are directly connected to one or more WP 0 switches. When a packet destined for arrives at a WP 1 switch the packet is randomly forwarded to a WP 0 switch. The network can have any number of waypoint levels. Once the maximum waypoint level is exceeded, the remaining switches are classified as inner ring ( IR ) and outer ring ( OR ) switches relative to . Inner ring switches are directly connected to the last waypoint level; all remaining switches are classified as outer ring switches. Inner ring switches randomly forward packets to a switch in the last waypoint level. Outer ring switches randomly forward packets to a switch from the set of neighboring switches with the shortest path to . Random forwarding (spraying) is based on ECMP hashing, such that packets from the same flow will not be reordered. Spraypoint routing requires all switches to have a full view of the network topology, in order to classify all pairs of switches. Section 5 of the paper describes CPU and memory requirements for Spraypoint. The take-home message is that off-the-shelf switches can support Spraypoint. Fig. 14 shows the bottom line: Source: https://arxiv.org/abs/2604.15261 Spraypoint allows the number of switches in a network to be reduced by 2-5x relative to a fat tree topology. ECMP hashing at each switch implies that this design goes to some length to avoid reordering packets within a flow. Recent work has shown that it is possible to relax this requirement (either in the NIC or the switch ). I wonder how Spraypoint could be improved if it was coupled with hardware like Falcon. Thanks for reading Dangling Pointers! Subscribe for free to receive new posts.

Programming

▲ 0

0 views

Dangling Pointers 3 weeks ago

Bonsai: Compiling Queries to Pruned Tree Traversals

Bonsai: Compiling Queries to Pruned Tree Traversals Alexander J Root, Christophe Gyurgyik, Purvi Goel, Kayvon Fatahalian, Jonathan Ragan-Kelley, Andrew Adams, and Fredrik Kjolstad PLDI'26 File this under: “so elegant, why wasn’t this discovered sooner?” This paper describes a generic language (Bonsai) and compiler for efficient tree traversals. The language is structured such that a simple compiler can quickly generate efficient code. The examples from the paper fall into two buckets: SQL-like queries and spatial data structures. Here is some example code from the paper which describes a SQL-like operation on a set of points: A is a structure with two elements ( , and ). The function returns the minimum associated with any point that has an x value within the range . And here is an example from the paper which describes a ray tracing function: The function finds all triangles which intersect a given ray and returns the one that is the closest to the origin of the ray. The key point of the paper is that both types of functions can be implemented as tree traversals. A key design point that makes Bonsai feasible is metadata stored in the trees which represent sets. Tree metadata is specified separately from queries. The following snippet from the paper contains a tree data structure represented as an algebraic data type: A set of points is represented as a tree. Leaf nodes hold points. Interior nodes have pointers to and children, and four pieces of metadata ( ). The keyword is used to describe the meaning of the metadata. The expression means that the value of all x fields in all points contained in the subtree lies within the range . The expression means that the minimum value of the field in any point in the subtree is . The Bonsai compiler takes a query and a description of the tree metadata as input and generates C++ code to perform the query via traversing the tree. There are three key properties of this process. The first is that the generated code for all filter and reduction operations are fused together. In other words, there are no intermediate trees (i.e., sets) produced during query execution. Secondly, tree metadata is used to accelerate both filtering and reduction operations. For filtering, the generated code checks tree metadata to determine if all data elements in a subtree will be accepted by the filter, or if all elements will be rejected by the filter. If all elements will be rejected, then there is no need to traverse the subtree. If all elements will be accepted, then there is no need for further evaluation of the filter expression for the subtree. In this case, traversal into the subtree can be skipped if the root of the subtree has metadata containing a pre-reduced value ( in the example above). Fig. 4 shows IR corresponding to two filtering examples. In both examples, there are two types of leaf nodes in the tree. nodes contain a single value whereas nodes contain an array of values. Fig. 4a shows the IR for a single filter expression . Here is the code, annotated with some comments to describe the semantics: Fig. 4b shows the IR for the logical and of two filter expressions: : Code generation tracks a symbolic interval associated with each expression. An interval is represented by two expressions: one that evaluates to the lower bound of the expression and one that evaluates to the upper bound. This interval analysis is used to produce the code that implements and . Interval analysis is fast to compile but can produce code that suffers from false positives. Symbolic interval analysis is general enough to handle spatial filters (e.g., those used in ray tracing). Fig. 7 compares Bonsai to a state-of-the-art library ( FCPW ) for geometric queries: Source: https://dl.acm.org/doi/10.1145/3808256 Fig. 8 compares Bonsai to relational databases for range joins. The range join logically computes the Cartesian product of two relations, and then removes elements from the result which are not near each other according to Manhattan distance . Source: https://dl.acm.org/doi/10.1145/3808256 Dangling Pointers A logical extension of this process would be to automatically determine what tree metadata would be most useful for a set of queries. Thanks for reading Dangling Pointers! Subscribe for free to receive new posts.

Programming Sql C++

▲ 0

0 views

Dangling Pointers 1 months ago

MatchBox: A Semantic Foundation for Data Plane Portability

MatchBox: A Semantic Foundation for Data Plane Portability Eric Hayden Campbell, Robert Zhang, Divyanshu Saxena, Aditya Akella, and Işıl Dillig PLDI'26 This paper identifies problems associated with subtle differences in match-action table implementations across hardware vendors and proposes some formalism to allow generic tooling to be implemented for match-action tables. A match-action table is a data structure present in some NICs and switches which specifies how packet-processing hardware should modify packets on the fly. This post on Gigaflow also discusses how a virtual switch can be implemented with match-action tables. Fig. 2 shows two match-action tables programmed in a hypothetical switch ( IP addresses in these tables are written in CIDR syntax ): Source: https://dl.acm.org/doi/10.1145/3808277 The syntax is clear but the semantics have an important footnote: switch S has a policy which causes packets that miss in the routing table to be dropped. Now imagine a switch ( ) from another vendor with a different policy: packets which cause a miss in the routing table are broadcast to all output ports. The task of porting the match-action tables from to in a way to preserves behavior is non-trivial. Fig. 3 contains a correct solution: Source: https://dl.acm.org/doi/10.1145/3808277 The difference is in the ACL table. The permissive allow entry has been replaced with two more restrictive entries that only allow packets that would not have triggered a miss in the routing table. One automated way to compute the contents of the ACL table for switch is an algorithm that looks at all pairs (i.e., the Cartesian product) of entries in the route and ACL table for switch , and then drops pairs that don’t make sense (e.g., the route and ACL addresses have no overlap). If you squint at that definition, it looks a lot like a relation join operation. In other words if you think of the ACL and routing tables as relations, then a way to compute the ACL table for switch would be to join the route and ACL tables for switch . The authors argue that relational algebra is almost the correct hammer for this nail, but not quite, and so this paper proposes Match Algebra . In Match Algebra, a match-action table can be thought of as a partial function which maps a valuation to an (action, valuation) pair. A valuation is just a set of bits (extracted from packet headers), and an action describes how a packet is to be modified. Another way to think of a match-action table is an ordered set of rules. A rule comprises: A guard, which defines the set of packets that match the rule An (action, valuation) pair Example guards could be: IPv4 packets with source address matching 10.2.1.0/24 UDP packets with a destination port of 15354 or 15355 An example (action, valuation) pairs could be: (replace the destination port, 15356) (pass the packet through unmodified, x) The set of rules is ordered such that if guards associated with multiple rules apply to a particular packet, the highest priority rule wins. The most important operators in the Match Algebra are: Sequential composition: modify the packet according to table , and use the result as input to table Preferential composition: Check to see if table has a rule matching the incoming packet, if so then apply that rule. Otherwise, use table to modify the packet. Parallel join: apply tables and to the input packet to generate two (action, valuation) pairs: , . Merge the results together. The merge operation requires that the results from and do not overlap (e.g., causes a destination port to be modified while causes destination address to be modified). The paper describes some other operators and presents formal semantics for Match Algebra. The paper describes which is a language (embedded in OCaml) which operates at the Match Algebra level of abstraction. Fig. 13 shows an example program which transforms match action tables with operators from Match Algebra: Source: https://dl.acm.org/doi/10.1145/3808277 Results The paper presents the following real-world use cases of : Transforming a set of match-action tables to an equivalent set with a different form (for porting rules between switches) Porting firewall rules between AWS, GCP, and Azure (which each have a different required structure) Translating system-wide eBPF tables to per-CPU eBPF tables Thanks for reading Dangling Pointers! Subscribe for free to receive new posts. Source: https://dl.acm.org/doi/10.1145/3808277 The syntax is clear but the semantics have an important footnote: switch S has a policy which causes packets that miss in the routing table to be dropped. Now imagine a switch ( ) from another vendor with a different policy: packets which cause a miss in the routing table are broadcast to all output ports. The task of porting the match-action tables from to in a way to preserves behavior is non-trivial. Fig. 3 contains a correct solution: Source: https://dl.acm.org/doi/10.1145/3808277 The difference is in the ACL table. The permissive allow entry has been replaced with two more restrictive entries that only allow packets that would not have triggered a miss in the routing table. One automated way to compute the contents of the ACL table for switch is an algorithm that looks at all pairs (i.e., the Cartesian product) of entries in the route and ACL table for switch , and then drops pairs that don’t make sense (e.g., the route and ACL addresses have no overlap). If you squint at that definition, it looks a lot like a relation join operation. In other words if you think of the ACL and routing tables as relations, then a way to compute the ACL table for switch would be to join the route and ACL tables for switch . The authors argue that relational algebra is almost the correct hammer for this nail, but not quite, and so this paper proposes Match Algebra . Match Algebra In Match Algebra, a match-action table can be thought of as a partial function which maps a valuation to an (action, valuation) pair. A valuation is just a set of bits (extracted from packet headers), and an action describes how a packet is to be modified. Another way to think of a match-action table is an ordered set of rules. A rule comprises: A guard, which defines the set of packets that match the rule An (action, valuation) pair IPv4 packets with source address matching 10.2.1.0/24 UDP packets with a destination port of 15354 or 15355 (replace the destination port, 15356) (pass the packet through unmodified, x) Sequential composition: modify the packet according to table , and use the result as input to table Preferential composition: Check to see if table has a rule matching the incoming packet, if so then apply that rule. Otherwise, use table to modify the packet. Parallel join: apply tables and to the input packet to generate two (action, valuation) pairs: , . Merge the results together. The merge operation requires that the results from and do not overlap (e.g., causes a destination port to be modified while causes destination address to be modified). Source: https://dl.acm.org/doi/10.1145/3808277 Results The paper presents the following real-world use cases of : Transforming a set of match-action tables to an equivalent set with a different form (for porting rules between switches) Porting firewall rules between AWS, GCP, and Azure (which each have a different required structure) Translating system-wide eBPF tables to per-CPU eBPF tables

Hardware Database Programming Ocaml

▲ 0

0 views

Dangling Pointers 1 months ago

Breadcrumb Filters: Fast Fully Featured Filters

Breadcrumb Filters: Fast Fully Featured Filters Andrew Krapivin, Aaditya Rangarajan, Alex Conway, Martin Farach-Colton, Rob Johnson, and Prashant Pandey SIGMOD'26 This paper presents the design of a breadcrumb filter , which is a membership testing data structure . Unlike a Bloom filter , a breadcrumb filter supports operations like deletion and merging. Breadcrumb filters also have the nice property that most operations access a single cache line (most of the time). A breadcrumb filter is a fingerprinting filter . Each item in a set is represented by its fingerprint (i.e., hash). Say a filter contains 1024 cache lines, and each cache line has storage for items. To insert an item into the filter, compute a 16-bit fingerprint of the item. Decompose that into a 10-bit integer (the cache line index) and a 6-bit integer (the remainder). Use the cache line index to determine which cache line to access. Find an empty slot in that cache line and place the remainder bits of the fingerprint into the empty slot to represent the item. A breadcrumb filter builds on top of these mechanics by cleverly dividing the filter storage into two sections: the front and back yards. The front-yard represents the fast path: each filter operation will touch one front-yard cache line. The backyard is only used to handle cases where a front-yard cache line fills up. The paper hyphenates “front-yard” but writes “backyard” as one word. The following pseudo-code illustrates how an item is inserted into a breadcrumb filter: A lookup operation follows a similar structure: To delete an item from a breadcrumb filter, it is sufficient to delete the item’s fingerprint . That wasn’t obvious to me up front. Imagine two items have the same fingerprint (hash). Inserting them both causes the same fingerprint to be inserted twice. Now, when one of them is deleted, it suffices to delete one of the copies of the fingerprint in the breadcrumb filter. The trick with deletion is that deleting a fingerprint from a front-yard cache line can require promoting an item from an associated backyard cache line. The real magic with breadcrumb filters comes in how items are moved between the front-yard and backyard. If a front-yard cache line is found to be full during insertion, then one item is moved to the backyard. That item could be the one that is currently being inserted, or it could be an item that was previously placed into the front-yard. The policy is: move the item which has the greatest value of the remainder bits . For example, if two items (A, and B) have remainder bits of 23 and 7, then item A will be moved to the backyard before B. This enables lookup operations to avoid touching backyard cache lines. For example, say the item that is being searched for has remainder bits = 23, and the (full) front-yard cache line contains items with remainder bits = [12, 5, 34, 3], there is no need to search the backyard. The “34” in the front-yard implies that no item with remainder bits value less than can be in the associated backyard cache lines. Note that this policy requires that delete operations sometimes move items from the backyard to the front-yard. The other trick is a mapping between front-yard and backyard cache lines which enables promotion of a deleted item from backyard to front-yard. Say each front-yard cache line is associated with two backyard cache lines, but those backyard cache lines are each associated with many front-yard cache lines. A front-yard cache line index is represented with 10 bits: The two backyard cache line indices associated with that front-yard cache line are: The key here is that very little information needs to be stored in the backyard in order to allow mapping from a backyard cache line index to a front-yard cache line index. To map backyard index back to , all one needs to know is the value of bit (which is stored in the backyard cache line). When an item is deleted from a front-yard cache line, the two associated backyard cache lines are searched for an item to be promoted back to the front-yard. Metadata (e.g., the value of bit ) is used to ensure that items are promoted back to the front-yard cache line from whence they came. Fig. 9 compares the throughput of the breadcrumb filter (BCF*) against other filters: Source: https://dl.acm.org/doi/10.1145/3786629 Dangling Pointers This design agrees with many others that the best one can do is read a single cache line for each lookup. I don’t have a better solution in mind, but it seems painfully slow if the filter doesn’t fit in cache. Thanks for reading Dangling Pointers! Subscribe for free to receive new posts.

Database Performance Programming

▲ 0

0 views

Dangling Pointers 1 months ago

RABIT: Efficient Range Queries with Bitmap Indexing

RABIT: Efficient Range Queries with Bitmap Indexing Junchang Wang, Fu Xiao, and Manos Athanassoulis SIGMOD'26 This paper presents an optimization for range filtering (e.g., ). File this under: “so crazy it might actually work”. This paper builds on the concept of a bitmap index . If the cardinality of a column is (i.e., there are distinct values in the column), then a bitmap index stores additional 1-bit columns along with the original column. These additional columns are called point bitvectors . The value in additional column is 1 for a particular row if the value in that row is the th distinct value. Here is an example column with 6 rows and 4 distinct values (0, 1, 2, 6). The header indicates that this is the value column. And here is the same column with 4 additional 1-bit wide rows attached. The header indicates columns that hold point bitvectors. To find all rows which have a value of 2, simply read the 3rd (i.e., ) bitmap column. Similarly, to find all rows which have a value of 6, simply read the 4th bitmap column. To efficiently support range queries, the authors of this paper propose adding even more columns that hold 1-bit values. These columns are called cumulative bitvectors . A cumulative bitvector holds the bitwise-or of a set of point bitvectors. In the example above, let’s create a cumulative bitvector (named ) for the values 0 and 1. The value of this column for a given row will be 1 if the value contained in the row is either 0 or 1. In other words: . Similarly, we can create a cumulative bitvector for the values 2 and 6 using the equation: . Here is the full turkey: A range query can be executed by reading one or more cumulative bitvectors and possibly a few point bitvectors. For example, to find all rows that have a value < 2, all one needs to do is read the value of . Cumulative bitvectors do not add much value in this toy example because each cumulative bitvector only aggregates data for two values, but you can see how this could work well with more aggregation. This trick can even be made to work for range queries that partially overlap with a cumulative bitvector. This whole scheme relies on the fact that point and cumulative bitvectors are highly compressible. This paper assumes the use of WAH compression . The executive summary of WAH compression is to divide each bitvector into words (e.g., 32 or 64 bit). One bit of each word is metadata that determines if the word is a or a . The remaining bits of a literal word contain raw (uncompressible bits). The remaining bits of a fill word contain a value and a length (run-length encoding). Fig. 9 compares throughput of this scheme (labeled GE in the figure) to other work. means each cumulative bitvector aggregates data for 20 point bitvectors. Performance looks good even for columns holding 100K distinct elements. Source: https://dl.acm.org/doi/10.1145/3769819 Table 3 compares the storage requirements for this scheme versus other indexing schemes that support range queries, which seems too good to be true. Source: https://dl.acm.org/doi/10.1145/3769819 Dangling Pointers I wonder if this idea could be generalized to other types of filtering, such as string operations (e.g., . Thanks for reading Dangling Pointers! Subscribe for free to receive new posts.

Database

▲ 0

0 views

Dangling Pointers 1 months ago

Accelerating Stream Processing Engines via Hardware Offloading

Accelerating Stream Processing Engines via Hardware Offloading Zhengyan Guo, Mingxing Zhang, Yingdi Shan, Kang Chen, Jinlei Jiang, and Yongwei Wu SIGMOD'26 This paper describes a trick to offload partitioning from CPU to NIC via clever use of RSS. The context of the paper is distributed systems for processing streaming queries, but the trick seems applicable to databases in general. Hash partitioning is a common divide-and-conquer technique to implement joins and aggregations. Here are some posts about papers that use this partitioning: SPID-Join: Skew-Resistant In-DIMM Joins Breaking Through the Memory Wall of OLTP Systems with PIM High-Performance Query Processing with NVMe Arrays: Spilling without Killing Performance Efficiently Processing Joins and Grouped Aggregations on GPUs RSS is a NIC feature whereby the NIC hashes select fields from incoming packet headers and uses the result to determine which CPU core to send the packet to. This enables efficient load balancing across CPU cores without reordering packets within a given flow (i.e., connection). Here is a previous post describing a clever way to extract more value out of RSS in cloud VMs: Enabling Fast Networking in the Public Cloud If you have many nodes cooperating to process a query, then the hash partitioning may span many nodes. For example, node A could hash the join/aggregation key of each row and then forward the row to either node B, C, or D, E depending on the hash value. This enables the join/aggregation work to be split across nodes B, C, D, and E. This is all fine and dandy from the perspective of node A. However, nodes B, C, D, and E likely have multiple CPU cores. How can one of these nodes execute their join/aggregation in parallel? The answer is recursive: partition the incoming rows again (using a different hash function) and have each CPU core process one of these smaller partitions. The paper focuses on the cost of partitioning the dataset, which can cost just as much as the partition join/aggregation step that follows it. The key insight is that the partition algorithm looks a lot like the RSS load balancing algorithm present in the NIC hardware. Here is the punchline: establish multiple network connections (using different ports) between node A and each of nodes B, C, D, and E. When node A partitions rows, it determines a specific connection (not node) to send each row to. This doesn’t improve performance at the sender, but it dramatically helps the receivers. Each receiver configures RSS such that all connections are spread across the CPU cores on the receiver. The NIC then distributes received packets to the appropriate CPU cores without any partitioning work on the receiving nodes. The one downside to this approach is load imbalances that occur due to data skew. If some join/aggregation keys are more common than others, then some CPU cores may be assigned more work than others. The paper proposes to dynamically monitor load imbalance at each receiver and reconfigure the RSS settings of the NIC to move connections off hot cores. Section 5 of the paper describes synchronization necessary to move a connection between cores in the middle of the query. This is a good mitigation, but as we’ve seen in this paper , RSS configuration is not uniformly exposed on cloud VMs. Fig. 8 has performance results across a number of benchmarks: Source: https://dl.acm.org/doi/10.1145/3769754 Dangling Pointers The solution is great, but asymmetric. I wonder if there is a way to get similar benefits on at the sending node (send side scaling)? Thanks for reading Dangling Pointers! Subscribe for free to receive new posts.

Database Performance Hardware

▲ 0

0 views

Dangling Pointers 2 months ago

F3: The Open-Source Data File Format for the Future

F3: The Open-Source Data File Format for the Future Xinyu Zeng, Ruijun Meng, Martin Prammer, Wes McKinney, Jignesh M. Patel, Andrew Pavlo, and Huanchen Zhang SIGMOD'26 F3 is a file format for columnar data (e.g., Parquet ) that is designed to be efficient and extensible. The optimizations make sense, the extensibility mechanism is ingenious , dangerous , fascinating. The key assumption made by this paper is that the hardware and software will continue to improve. It is hard to argue with that. The trouble is that interoperable formats like Parquet take a snapshot of the state-of-the-art and freeze it in a specification. Some innovations that are invented after the format is frozen are incompatible with existing formats because they require a different data layout. Section 1 of the paper refers to many examples related to compression, indexing, and filtering. The goal of F3 is to be general enough to allow seamless incorporation of future innovations without changing the F3 spec nor F3 decoder implementations. Fig. 2 illustrates an F3 file: Source: https://dl.acm.org/doi/10.1145/3749163 A file consists of a metadata and a set of row groups. A specific row group contains data for all columns and a subset of rows. F3 contains incremental improvements over existing columnar formats, for example: F3 metadata supports random access, which is important for operations that only need to access a smaller percentage of all columns. F3 decouples file I/O from a row group storage. The rows associated with a given column in a row group are further subdivided into , which are actually stored. This allows row groups to be sized for efficient row-group level filtering, while the IO unit size is tuned to minimize working set while also amortizing the fixed costs associated with file I/O. F3 allows flexible . Each IO unit can contain a dedicated dictionary, or multiple IO units can share a dictionary. Columns with low cardinality will benefit from smaller dictionary scopes, whereas columns with high cardinality do better with larger dictionary scopes. The stand-out feature for F3 is the yellow block in the block. The idea is that an F3 file can contain within it the WebAssembly code needed to decode the encoded values in an IO unit. If someone invents a brilliant new encoding method that works well with some data sets, they can ship the decoder right along with the data set. Storage of the WASM code shouldn’t be too much of an issue, because the storage cost is amortized across all row groups. The big questions are performance and security. Section 6.2 has some comments on this. In theory, the WASM specification is air-tight, and a bug-free implementation should be able to securely run arbitrary WASM code in-process. WASM also supports performance optimizations like parallel compilation and SIMD instructions. Something I don’t see in the paper is a discussion about how filtering interacts with WASM decoding. I suppose the extensibility could only be used for decoding, and filtering could be hard coded into F3, but that seems against the extensible spirit of F3. Fig. 11 shows the working set reduction from decoupling IOUnit size from row group size: Source: https://dl.acm.org/doi/10.1145/3749163 Table 3 shows how flexible dictionary scopes allow one to trade encoding time for compression ratio (lower relative CR numbers mean smaller files on disk): Source: https://dl.acm.org/doi/10.1145/3749163 Fig. 15 quantifies WASM overhead by comparing decode time for hard coded F3 decoder implementations vs the same algorithms expressed in WASM: Source: https://dl.acm.org/doi/10.1145/3749163 Fig. 16 shows potential savings associated with using WASM extensibility to implement a custom decoder from the literature. Source: https://dl.acm.org/doi/10.1145/3749163 Dangling Pointers I wonder how well WASM decoders can be implemented on other hardware architectures. Is WASM the ideal language for expressing this, or convenient standard that already exists? Thanks for reading Dangling Pointers! Subscribe for free to receive new posts. Source: https://dl.acm.org/doi/10.1145/3749163 A file consists of a metadata and a set of row groups. A specific row group contains data for all columns and a subset of rows. F3 contains incremental improvements over existing columnar formats, for example: F3 metadata supports random access, which is important for operations that only need to access a smaller percentage of all columns. F3 decouples file I/O from a row group storage. The rows associated with a given column in a row group are further subdivided into , which are actually stored. This allows row groups to be sized for efficient row-group level filtering, while the IO unit size is tuned to minimize working set while also amortizing the fixed costs associated with file I/O. F3 allows flexible . Each IO unit can contain a dedicated dictionary, or multiple IO units can share a dictionary. Columns with low cardinality will benefit from smaller dictionary scopes, whereas columns with high cardinality do better with larger dictionary scopes.

Data Analysis Open Source Database

▲ 0

0 views

Dangling Pointers 2 months ago

Enabling Packet Spraying over Commodity RNICs with In-Network Support

Enabling Packet Spraying over Commodity RNICs with In-Network Support Xiangzhou Liu, Wenxue Li, Zihao Wang, and Kai Chen EUROSYS'26 This paper proposes changes to top-of-rack (ToR) switch hardware to enable packets from a single flow to utilize many network paths ( Falcon offers a similar benefit via changes to the NIC rather than the switch). The Falcon approach is robust but more invasive. The switch-based approach from this paper is a more incremental change. The sweet spot for packet spraying is a data center that has a large number of network paths compared to network flows (i.e., connections). In such an environment, there is an incentive to spray the packets associated with one flow across multiple paths. The trouble with packet spraying is that packets will commonly arrive out-of-order. The system has to be able to distinguish the out-of-order case from genuine packet loss. Section 2.2. of the paper describes three techniques for handling packet loss: PFC - the trouble is that this has scalability limits, and only addresses packet loss due to buffer overflows (not angels flying down and flipping your bits) Timeouts - the trouble is that practical timeout values have to be large Selective Repeat Selective repeat is a feature of modern RDMA NICs which is similar to the bitmaps tracked by Falcon hardware. The idea is that a receiving NIC tracks an expected sequence number (ePSN) for each flow. If a packet arrives with a sequence number greater than (but not too much greater than) the ePSN, the NIC accepts it and records this fact in a per-flow bitmap. The receiving NIC then sends a NACK to the sender, requesting that the sender resend the packet corresponding to the ePSN. In the out-of-order case, this NACK is unnecessary as the expected packet will arrive soon enough. The question asked by this paper is: can one easily modify switch hardware to filter the unnecessary NACKs? The core idea proposed by this paper is that the NICs and switches agree on the number of paths for a particular flow. Sending NICs use a packet’s sequence number to determine which path to use (e.g., . The switch can then track information for each path associated with each flow. When a NACK arrives at a switch, the switch can drop the NACK as necessary (thus avoiding unnecessary retransmissions). For example, say there is a single flow mapped to 4 paths. Packets with PSNs [0, 4, 8, 12, …] will travel over path 0. Packets with PSNs [1, 5, 9, 13, …] will travel over path 1. If packets arrive at the receiving NIC in this order: [0, 1, 5 , 4] the NIC will send a NACK when it receives packet 5. However, the switch will drop that NACK because it “knows” that no packet has been received out of order with respect to its flow. Fig. 12 has simulated performance results for collective operations common in AI workloads. is the work described in this paper. CCT is a measure of how long the collective operation took. Source: https://dl.acm.org/doi/10.1145/3767295.3803588 Dangling Pointers This feels like an engineering solution to a business problem of how to get many NIC vendors to align on a packet spraying solution. I suspect there are many applications where it would not be too difficult to introduce multiple flows. For example, in a machine learning workload, the weights/deltas associated with layer could be assigned to flow . This would increase network path utilization without any hardware changes. Thanks for reading Dangling Pointers! Subscribe for free to receive new posts. PFC - the trouble is that this has scalability limits, and only addresses packet loss due to buffer overflows (not angels flying down and flipping your bits) Timeouts - the trouble is that practical timeout values have to be large Selective Repeat

Performance Hardware Cloud

▲ 0

0 views

Dangling Pointers 2 months ago

LightDSA: Enabling Efficient DSA Through Hardware-Aware Transparent Optimization

LightDSA: Enabling Efficient DSA Through Hardware-Aware Transparent Optimization Yuansen Wang, Teng Ma, Yuanhui Luo, Dongbiao He, Zheng Liu, and Yunpeng Chai EUROSYS'26 This paper describes performance characteristics of the Intel DSA hardware accelerator, and software techniques to maximize performance when using DSA. My takeaway is: the DSA supports a variety of convenience features, but each one is so expensive that you are better off adding software complexity to avoid these paths. The Data Streaming Accelerator ( DSA ) is a hardware accelerator in recent Intel chips. It can implement simple memory operations like , , , and CRC generation. Fig. 2 contains a high-level diagram of the DSA architecture. Source: https://dl.acm.org/doi/10.1145/3767295.3769356 Operations are written into work queues as 64-byte descriptors. A work descriptor (WD) describes a single operation, whereas a batch descriptor (BD) references many work descriptors. A batch is the fundamental unit of control (the DSA signals the CPU when a batch has completed). The DSA contains multiple engines and arbiters to spread work across the engines. Source and destination buffers accessed by the DSA do not need to be pinned into memory, the DSA can handle page faults. The DSA supports demand faulting via the page request service (PRS). This enables the DSA to send an interrupt to the OS (via the IOMMU) requesting the OS to resolve the fault. This paper reports a similar finding to a previous paper looking at the PCIe page request interface: demand faulting is convenient, but slow. The LightDSA authors recommend that software forcibly fault in pages before submitting descriptors. The DSA supports operations that require unaligned reads and writes of data from/to DRAM but the authors find that 64-byte aligned accesses are much faster. Fig. 8 has some numbers, even 32-byte alignment is expensive (compare the light green and dark green bars). Source: https://dl.acm.org/doi/10.1145/3767295.3769356 The authors recommend having software ensure that all writes performed by the DSA are 64-byte aligned. Software can do this by executing the operation for the first few bytes of each task, up until the destination buffer is 64-byte aligned. Like many HW/SW interfaces, the DSA writes both result data and metadata to memory. Result data is associated with each work descriptor, while completion metadata is associated with each batch descriptor. Metadata is read by software to learn when an operation completes. In such a scheme, it is important that software observes the batch metadata write after the result writes have completed. If the metadata write can land first, then software may try to read the result buffer before it has actually been updated. The DSA supports multiple traffic classes (TC). As with discrete PCIe accelerators, writes from the DSA associated with the same traffic class will land in host memory in order (these are posted writes ). However, writes associated with different TCs may be reordered. Here is a previous paper that describes performance problems with reordering. Section 3.8 of the DSA architecture specification describes two choices that software developers have. Either they should configure work descriptors and batch descriptors to use the same traffic class, or they should configure the DSA to enforce ordering via the (readback) flag. When that flag is set, the DSA will ensure that all result writes have landed in host memory by issuing a read request to read the most recently written result data back to the DSA, waiting for the response to come back, and then issuing metadata writes associated with the batch descriptor. Discrete PCIe devices can use the same trick to enforce ordering across traffic classes. Fig. 7 shows the performance cost of using this feature: Source: https://dl.acm.org/doi/10.1145/3767295.3769356 My takeaway is that DSA users should ensure that work and batch descriptors use the same traffic class, to avoid having to invoke this slow read-back path. Because the DSA contains multiple engines, tasks can complete in a different order than the order in which they are submitted. This is fine in itself, but the authors note that software must take care to efficiently support allocating work and batch descriptors in light of this. Time spent bookkeeping to handle out-of-order completion is overhead that adds up for small tasks. The solution proposed by this paper is for software to maintain two batch descriptor lists (free, and busy). When software needs to recycle descriptors from the busy list to the free list, it checks most (but not all) batch descriptors in the busy list to see if the hardware has completed the batch. This is in contrast to an approach which simply checks to see if the oldest-submitted batch has completed. The paper finds that it is optimal for the recycling process to ignore the 25 most recently submitted batch descriptors but check the completion status of all other outstanding batches. Figs. 12 and 13 compare the performance you can expect to see from using DSA naively versus using the techniques described in this paper (LightDSA). My takeaway is that the DSA is powerful, but only if you use it carefully. Source: https://dl.acm.org/doi/10.1145/3767295.3769356 Dangling Pointers I suspect the elevator pitch for DSA is something like: “just re-compile your existing C/C++ code and all of the memcpy/memcmp time will be optimized out”. It seems like DSA falls short of that. I wonder if the elevator pitch would be better realized if application code was written in other languages (like an explicitly pipeline parallel language). Thanks for reading Dangling Pointers! Subscribe for free to receive new posts.

Hardware Performance C++

▲ 0

0 views

Dangling Pointers 2 months ago

Accelerating Transactional Execution via Processing-In-Memory

Accelerating Transactional Execution via Processing-In-Memory André Lopes, Daniel Castro, and Paolo Romano EUROSYS'26 This paper describes a way to implement OLTP for a processing-in-memory architecture. As with other academic research, it uses UPMEM ( here are two summaries of papers that rely on UPMEM). Something I found surprising in this work is conflicts can cause transactions to abort, even if all transactions only access data in the same UPMEM bank. A UPMEM DIMM is like a DRAM DIMM, but each bank contains a multi-threaded in-order core which can access data from the bank it is co-located with. This paper calls these processors DPUs (some other papers call them IDPs). The only way for two DPUs to communicate with each other is for the host CPU to read data from one bank and write it into another. The system described in this paper is called PIM-TIDE. It assumes that transactions come pre-sliced into computational graphs comprising subtransactions. A single subtransaction only accesses data within one bank (and thus executes on a specific DPU). Users of PIM-TIDE do not need to know exactly which data words a subtransaction will access, but they do need to be able to restrict a subtransaction to only access data from a specific bank. This works well on TPC-C style transactions where most of the database can be partitioned on . The host CPU groups transactions into batches and sends work to the DPUs one batch at a time. Within a batch, transactions are categorized into two groups: Local transactions execute entirely within a DPU Distributed transactions execute across multiple DPUs All subtransactions associated with distributed transactions within a batch are assigned a unique sequence number, which determines the order in which the subtransactions will commit. Local transactions are not preassigned to a commit order. DPUs first process all distributed subtransactions in a batch and then execute all local subtransactions. Algorithm 3 illustrates PIM-TIDE’s concurrency control scheme for dealing with intra-DPU conflicts between subtransactions. is stored in fast on-chip memory and is indexed by a hash of the word address. If a transaction aborts, state can be rolled back and the transaction is retried. All transactions assigned to a DPU will commit eventually. Inter-DPU conflicts are handled by deterministic concurrency control (i.e., the pre-assigned sequence numbers). Source: https://dl.acm.org/doi/10.1145/3767295.3803621 Results Fig. 3 compares performance of PIM-TIDE vs a CPU baseline for a mix of TPC-C transactions, wow that is a significant speedup. I believe all transactions/subtransactions are written by hand in C code that is compatible with UPMEM DPUs. Source: https://dl.acm.org/doi/10.1145/3767295.3803621 Dangling Pointers TPC-C is easy to partition; I wonder how well PIM-TIDE does on workloads that are not as partitionable. Also, this scheme doesn’t seem to allow for interactive transactions, how important are those in the real world? Thanks for reading Dangling Pointers! Subscribe for free to receive new posts. Local transactions execute entirely within a DPU Distributed transactions execute across multiple DPUs

Database C Hardware Performance

▲ 0

0 views

Dangling Pointers 2 months ago

Yield Not Thy Core

Yield Not Thy Core Achilles Benetopoulos, Peter Alvaro, Andi Quinn, and Robert Soule EUROSYS’26 This paper describes a solution to the placement problem in distributed systems. If you model a computation as a directed graph, how do you optimally distribute the graph among a set of cooperating computers? The authors propose a dynamic placement system and implement it in Magpie . One common solution to the placement problem is to ship data over the network. For example, a set of compute nodes could access data via network requests to a separate set of nodes running Redis servers. At the opposite end of the spectrum, code can be shipped over the network. The canonical example is expressing computation as a SQL query which is sent to the node(s) that hold the relevant data. Magpie proposes a more fluid solution, where both code and data can move dynamically. In Magpie, an object represents data that is operated on. What makes Magpie objects unique is that pointers to data stored in an object are encoded as tuples. This allows Magpie to dynamically move objects around the system without invalidating pointers. The downside of this approach is that it prevents traditional libraries (that rely on raw pointers) from being used in user code. Magpie assumes a high degree of inter-object locality, so any given object is stored by exactly one node (i.e., a single object is never split between multiple nodes). User code is expressed in terms of nanotransactions and epics . A nanotransaction runs to completion on a single node and accesses a pre-specified set of objects. The Magpie runtime ensures that all objects accessed by a given nanotransaction are resident on a single node before executing the nanotransaction. The code for a nanotransaction is simple, because there is no need to query data over the network, and there is no need to deal with locking. If a hazard is present between two nanotransactions, they will execute serially. In Magpie, nanotransactions are written in Rust. An epic is a computation graph where each vertex is a nanotransaction and each edge is a data dependency. In contrast to nanotransactions, a single epic can be distributed across multiple nodes. Magpie schedules nanotransactions once all data dependencies are satisfied. Conflicts between concurrently running epics are handled via snapshot isolation . Any particular epic has a consistent view of each object and may abort in the event of a conflict. Scheduling and data movement are implemented hierarchically. A worker node can locally determine if it has ownership of all dependencies required for a nanotransaction. If this is the case, then the worker node executes the transaction immediately. Otherwise, the worker node uses a local ownership cache to try to determine if another node has all required dependencies and communicates with that node if possible. Failing that, scheduling is performed by a global orchestration node. Fig. 9 compares Magpie to memcached executing a workload that involves a user-specified read-modify-write operation: Source: https://dl.acm.org/doi/10.1145/3767295.3803616 Magpie is able to offer a lower latency because it is able to ship the entire read-modify-write operation to the server that holds the relevant data, rather than requiring multiple roundtrips. Some applications may benefit from being able to indicate that an object is rarely changed and thus can be distributed among multiple nodes at the same time. Thanks for reading Dangling Pointers! Subscribe for free to receive new posts.

Sql Cloud Rust Programming

▲ 0

0 views

Dangling Pointers 3 months ago

Pipeline Parallel Decompression

This isn’t a paper summary, but rather a description of a hobby experiment I’ve been hacking on ("research quality" code). This quote (attributed to either Anonymous or David Clark ) originally referred to networking, but applies to parallel programming as well: There is an old network saying: Bandwidth problems can be cured with money. Latency problems are harder because the speed of light is fixed—you can’t bribe God. Standard "cured with money" parallelization techniques (e.g., shared-nothing architectures, data parallelism) try to minimize cross-core communication. These hammers are great for hitting nails labeled: "improve throughput by throwing more cores at the problem”. Not everything is a nail. Important problems which cannot be solved with this kind of approach include: Parallel network packet processing in cases where load balancing schemes like RSS do not apply Parallel transaction processing when there is high contention between transactions Parallel encryption of a single stream of data Pipeline parallelism has the potential to provide "bribing God” solutions to some of these problems. A potential additional benefit that pipeline parallelism brings to the table is better usage of CPU caches because of a smaller working set. For example, if 8 cores cooperate to process 1 input file, the working set (input data, output data, intermediate data structures) is potentially 8 times smaller than the case where each core processes a separate input file. This caching advantage also applies to instruction caches, as pipeline parallelism distributes the computational steps of an algorithm across cores. Pipeline parallelism has some major drawbacks: Fine-grain synchronization/communication Load imbalance The purpose of this experiment is to put some numbers on the costs and benefits in a real-world application ( DEFLATE decompression). DEFLATE decompression is hard to parallelize because of two tight feedback loops: The position of encoded token in the input stream is not known until token is decoded (because input data is encoded with a variable length code). The output generated by a match (i.e., length & distance tuple) cannot be computed until some amount of previous output has been generated (because a match references previously generated output) A Negative Nancy might view these as problems, but a Positive Pipeliner views them as a guide for how to decompose the algorithm into pipeline stages. The general technique is to dedicate a pipeline stage to each of these feedback loops and whittle them down to be as tight as possible. The design I’ve landed on has three pipeline stages: , , and . The stage computes the length of each encoded token. It simply reads the next 13 bits from the input stream and uses them as an index into a lookup table. The inner loop looks like this: Note that in contrast to non-pipelined implementations, the only thing this code (and the lookup table) are concerned with is finding the length of each token, everything else is dealt with in another pipeline stage. Each iteration of this loop runs in about 8 clock cycles, and the lookup table fits in the L1 cache. The CPU cannot run multiple iterations of this loop in parallel due to the tight dependency chain. The input to the lookup stage is the encoded bits associated with each input token ( in the code above). These bits are used to perform another lookup (in a larger lookup table, stored in the L2 cache) which results in much more information about each token. Optimizing this stage is easy, because it doesn’t contain any tight feedback loops. The CPU can process multiple loop iterations in parallel, which enables it to hide the latency of accessing the L2. If necessary, it would be easy to split this pipeline stage into two. The inner loop looks like this: The structure contains metadata about the input token (literal value and/or information about a match). This data structure does not contain the exact distance associated with the match, the variables named deal with that detail from the DEFLATE spec. The stage writes literals and matches to the output buffer. This code leans on the CPU store-to-load forwarding hardware to deal with match operations which must read data that was recently produced. Each iteration of the inner loop performs a word-sized write of literal data, plus a 32B read and write to read and write match data. Actual store-to-load forwarding is rare, as most match distances are large. The Silesia Corpus contains commonly used files to benchmark compression algorithms. has English text with short matches whereas contains data dumps with longer matches. is an optimized library which can decompress roughly 2-3x faster than the standard . The following chart shows baseline performance on in a shared-nothing architecture where each CPU core decompresses a separate input file. There is one data point for each core count (1, 2, …, 8). As you would expect, throwing more cores at the problem improves throughput, at the cost of slight latency increase. If you want a more interesting tradeoff of throughput vs. latency, you have to bribe God. For example, say you are writing a decompression application. If the user requests a bulk decompression of 100 files, then the optimal choice may assign each file to a CPU core. But if the user requests to decompress a single file, then you would prefer to decompress using multiple CPU cores. And here is the same chart with the 3-stage pipeline implementation added in orange (compare it to the third blue dot from the left for a 3-core vs 3-core comparison): For a 37% cost in throughput, you get a 2x reduction in latency. Here is the chart for , which shows a similar story. Data-parallel throughput saturates at 6 cores. Pipeline parallelism allows a 2.6x latency reduction at the cost of 14% throughput. Dangling Pointers I think there is room for language/runtime support to improve performance of pipeline parallel algorithms on multicore CPUs (by reducing load imbalance). is bound by the chase stage, whereas is bound by the output stage. The programmer could supply multiple implementations of the pipeline (with some compiler help to reduce code duplication), and the runtime could dynamically switch between them depending on which stage is the bottleneck. High level synthesis tools are capable of automatic pipelining. Such techniques could be used to automatically generate many pipeline implementations for the runtime to choose between. The description above leaves out a few implementation details regarding the lookup tables. Because the lookup table data is spread across two cores (i.e., pipeline stages), there is enough room to store data for 2 Huffman tokens (2 literals, or a full match). This provides a large speedup compared to traditional implementations that store all data in the caches of a single core. Because the stage is throughput bound rather than latency bound, it can afford to access the lookup table via a layer of indirection. The 13 input bits are used to lookup a index, and that index is used to access the final data in another lookup table. The second lookup table has fewer entries, but each entry is larger. This reduces the total working set. This design leans heavily on CPU branch prediction. The code snippets shown earlier are for the common cases, with branches used to implement uncommon cases (e.g., a single encoded token that is wider than 13 bits). As long as those cases are rare, branch prediction does a great job of keeping the inner loops humming. An interesting puzzle arose during this experiment. I found that performance could swing widely (~10%) based on where the operating system located stacks of the various threads. The stack address would change from run to run because of ASLR . A little to offset the stack by a small amount would resolve this issue. It seems to be an important consideration when trying to maximize usage of the L1 cache. Subscribe now Parallel network packet processing in cases where load balancing schemes like RSS do not apply Parallel transaction processing when there is high contention between transactions Parallel encryption of a single stream of data Fine-grain synchronization/communication Load imbalance The position of encoded token in the input stream is not known until token is decoded (because input data is encoded with a variable length code). The output generated by a match (i.e., length & distance tuple) cannot be computed until some amount of previous output has been generated (because a match references previously generated output)

Performance Programming

▲ 0

0 views

Dangling Pointers 3 months ago

SG-IOV: Socket-Granular I/O Virtualization for SmartNIC-Based Container Networks

SG-IOV: Socket-Granular I/O Virtualization for SmartNIC-Based Container Networks Chenxingyu Zhao, Hongtao Zhang, Jaehong Min, Shengkai Lin, Wei Zhang, Kaiyuan Zhang, Ming Liu, and Arvind Krishnamurthy ASPLOS'26 SR-IOV is a PCIe feature that enables a single device to expose multiple virtual functions, each of which appears as a separate device. This can be used to securely share one hardware device among multiple virtual machines. For containerized workloads, one would think that SR-IOV could be used to expose a virtual NIC to each container. This would save CPU cycles as network virtualization would be handled by the NIC rather than software. The trouble is that SR-IOV doesn’t scale to high container counts (they top out on the order of 100 of virtual functions per physical NIC). This paper introduces Socket-Granular I/O Virtualization (SG-IOV) which enables NIC virtualization at the socket level . The authors have an implementation working on NVIDIA BlueField-3. The key assumption that SG-IOV makes is that container networking uses stream sockets (e.g., TCP) rather than datagram sockets (e.g., UDP). In other words, software running inside a container wants to reliably send a stream of bytes rather than a stream of packets. Streams are transmitted through Warp Pipes , which are simply ring buffers (comprising a base address, head and tail pointers). Warp Pipes can be stored in host memory or NIC local memory. A socket is associated with one or more dedicated Warp Pipes. A server can have thousands of Warp Pipes, because the low-level NIC hardware (which may have scalability limits) doesn’t directly interact with Warp Pipes. Updates to head and tail pointers are not performed directly via memory writes, instead they are communicated through a Cross-FIFO . A single message in a cross-FIFO contains three fields: Ring buffer ID (which Warp Pipe to update) Which pointer to update (head or tail) The new value of the head or tail pointer There are multiple implementations of the Cross-FIFO interface. For example, the authors use a PCIe-based implementation for host→NIC communication, and a RDMA based implementation for NIC→NIC communication. Each cross-FIFO uses limited NIC resources; therefore many sockets share a single cross-FIFO, which is OK because the messages they contain are coarse-grain (e.g., increment tail pointer by 16KiB). Say an application in container A on host 1 wants to send 8KiB of data to an application in container B on host 2. The flow looks like this: Host CPU (host 1): The application calls the standard socket API The payload is copied into the Warp Pipe associated with the socket A message is enqueued into a PCIe cross-FIFO, indicating that the head pointer should be incremented by 8KiB ARM CPU running on the NIC (host 1): Dequeue the message from the cross-FIFO, update the head pointer Enqueue task descriptors to the low-level NIC hardware to read the payload data (i.e., local DMA) from the Warp Pipe and store it in the correct Warp Pipe on host 2 (i.e., RDMA); note that these task descriptors can configure the NIC to perform appropriate network virtualization After the data has been transmitted, enqueue a message to the NIC on host 2 (via a RDMA-based cross-FIFO) to update the head pointer for the Warp Pipe on host 2 ARM CPU running on the NIC (host 2): Dequeue the message from the cross-FIFO Update the local head pointer Enqueue a message to the host CPU (host 2) via a PCIe-based cross-FIFO, indicating that the head pointer should be incremented Host CPU (host 2): Dequeue the message from the PCIe-based cross-FIFO Send data to the application when it calls And a similar sequence would update tail pointers. The key design principles of SG-IOV are: All state is tracked by software running on the host CPU and ARM CPUs running on the NIC All low-level NIC hardware is used in a stateless manner, and is multiplexed across many sockets A benefit of this design is that it is flexible enough to handle the loopback case efficiently. Section 8 of the paper shows that SG-IOV enables the use of hardware-accelerated network virtualization (saving host CPU cycles) while offering latency and bandwidth that is competitive with other container-based network virtualization systems. Figs. 17 and 18 show latency and bandwidth numbers for a few benchmarks: Source: https://dl.acm.org/doi/10.1145/3779212.3790218 Dangling Pointers It seems like one downside of this system is excessive memory usage. If each socket has dedicated large ring buffers, then DDIO may not be effective (see here , here , and here for other papers that discuss this problem). Subscribe now Ring buffer ID (which Warp Pipe to update) Which pointer to update (head or tail) The new value of the head or tail pointer The application calls the standard socket API The payload is copied into the Warp Pipe associated with the socket A message is enqueued into a PCIe cross-FIFO, indicating that the head pointer should be incremented by 8KiB Dequeue the message from the cross-FIFO, update the head pointer Enqueue task descriptors to the low-level NIC hardware to read the payload data (i.e., local DMA) from the Warp Pipe and store it in the correct Warp Pipe on host 2 (i.e., RDMA); note that these task descriptors can configure the NIC to perform appropriate network virtualization After the data has been transmitted, enqueue a message to the NIC on host 2 (via a RDMA-based cross-FIFO) to update the head pointer for the Warp Pipe on host 2 Dequeue the message from the cross-FIFO Update the local head pointer Enqueue a message to the host CPU (host 2) via a PCIe-based cross-FIFO, indicating that the head pointer should be incremented Dequeue the message from the PCIe-based cross-FIFO Send data to the application when it calls All state is tracked by software running on the host CPU and ARM CPUs running on the NIC All low-level NIC hardware is used in a stateless manner, and is multiplexed across many sockets

Performance Hardware Docker

▲ 0

0 views

Dangling Pointers 3 months ago

Efficient Remote Memory Ordering for Non-Coherent Systems

Efficient Remote Memory Ordering for Non-Coherent Systems Wei Siew Liew, Md Ashfaqur Rahaman, Adarsh Patil, Ryan Stutsman, and Vijay Nagarajan ASPLOS’26 It seems like every year there is a new PCIe standard which doubles bandwidth. The key takeaway from this paper is that these improvements are for the fast path , but there exist use cases which are crippled by details of the PCIe protocol. This paper describes two inefficiencies caused by the current protocol and suggests improvements to address them. From my experience, here is the canonical way for the host X64 CPU to send a request to a PCIe device and receive a response. First, the request payload is stored in host memory (which can be mapped as CPU cacheable). During this time, the device does not read any of the payload. Next, a handful of MMIO writes (to uncacheable memory) are used to point the device to the payload and kick off the work. The device stores results via posted DMA writes to host memory. After producing all results, the device uses more posted DMA writes to update control information in host memory. Finally (and optionally), the device signals an interrupt. From the perspective of the device, the interrupt is another posted DMA write to the host. Posted DMA writes are visible to the host in the order they are issued. In other words, the host is guaranteed that it will only observe the control information update after the response payload has been written. Similarly, the host will receive the interrupt after the control information is written. The problems identified by this paper are caused by a lack of ordering guarantees. Table 1 illustrates where ordering is enforced today: Source: https://dl.acm.org/doi/10.1145/3779212.3790156 W→W ordering means two writes from a device will appear to land in host memory in the order they were issued. W→R means that if a device writes to an address in host memory, and then issues a read, the read response will contain the updated data. For more details there is a great explainer on a LinkedIn post here . PCIe has provisions that allow devices to relax these ordering guarantees, but there is no way to enforce more ordering. “R→R No” means that if a device issues two DMA read requests, the read response data could appear as if the reads occurred in the wrong order. This matters for scenarios where the host CPU is actively writing to the same data structures that the device is reading from. Imagine an application that involves two data structures: An array of data: An array of flags: is only valid if is set. Carefully written software could update these data structures, ensuring that is set only after the associated data is written. The trouble is there is no efficient way for a PCIe device to pipeline reads of and . For a given , the device has no choice but to read , wait for the response, and then issue the read of . Some systems work around this by ensuring that data and metadata are stored in the same cache line. A more realistic application is a key-value store that is concurrently updated by the host CPU and read by a device (i.e., RDMA reads from a NIC). It is hard to develop such a system in a way that offers strong consistency and high performance. The solution proposed by the authors is to add semantics similar to and to PCIe. A read TLP with the bit set would not be reordered past subsequent reads. A write TLP with the bit set would not be reordered before prior writes. The other inefficient scenario described by this paper is caused by the lack of W→W MMIO ordering. The problem here is in the CPU architecture. On x86, an MMIO region can be mapped as write-combined, but the application must issue expensive instructions to ensure that writes appear in the correct order. This restricts MMIO writes to low-bandwidth scenarios. The architectural solution described by this paper is to add four explicit MMIO instructions to the ISA: MMIO-Release MMIO-Acquire MMIO-Store and MMIO-Release are store instructions. MMIO-Release has release semantics (it will not be reordered before prior stores). MMIO-Load and MMIO-Acquire are load instructions. MMIO-Acquire instructions are not reordered after subsequent loads. The authors note that RISC-V has similar instructions, but they involve the CPU stalling to implement the desired memory ordering. The solution offered by this paper instead involves a re-order buffer in the PCIe root complex. The CPU assigns sequence numbers to MMIO operations, and the root complex uses those sequence numbers to restore operations to their correct order. Fig. 6 has simulation numbers projecting speedups an RDMA-based key-value store could see if it could properly pipeline DMA reads. and are the work described by this paper. assumes additional speculative optimizations in the root complex. Source: https://dl.acm.org/doi/10.1145/3779212.3790156 Fig. 10 shows how fast a single core can perform unordered MMIO writes. The idea is that if the CPU architecture is enhanced to allow an application to express just the right amount of ordering, it could be possible for a single core to write packet data as fast as a NIC can consume it. Source: https://dl.acm.org/doi/10.1145/3779212.3790156 Dangling Pointers The paper ends with this food for thought: By establishing a high-performance baseline for non-coherent I/O, this work raises the question of whether the complexity of coherent interconnects (like CXL) is truly necessary for future host-device communication. Thanks for reading Dangling Pointers! Subscribe for free to receive new posts. An array of data: An array of flags: MMIO-Release MMIO-Acquire

Performance Hardware

▲ 0

0 views

Dangling Pointers 3 months ago

Performance Predictability in Heterogeneous Memory

Performance Predictability in Heterogeneous Memory Jinshu Liu, Hanchen Xu, Daniel S. Berger, Marcos K. Aguilera, and Huaicheng Li ASPLOS'26 This paper presents a system named CAMP, which can be used to predict how the performance of a particular workload will be affected by moving the workload from local DRAM to remote DRAM accessed over CXL. Just collect some performance counters when running your workload on local DRAM, and you can predict how your workload will run on remote DRAM. In machine learning vernacular: CAMP derives a set of features from the values of Intel PMU counters collected while running an application out of local DRAM. Plug those feature values into a pre-trained model, and you can predict how much slower the application will run on CXL. The model is somewhat the opposite of a DNN; it has 5 weights! The values of those weights are learned by running a suite of microbenchmarks on the test hardware. The high-level model is adopted from previous work . The slowdown percentage associated with moving a workload to CXL memory is the sum of three factors: Slowdowns due to store buffer stalls Slowdowns due to demand read stalls Slowdowns due to line fill buffer (LFB) utilization A typical processor can commit a store instruction when the store data & address are placed in the store buffer (a local queue). This allows the processor to keep humming before the store lands in memory. The processor will stall however if the store buffer fills up. On CXL systems, stores that require a read-for-ownership (RFO) are a frequent cause of backpressure. If the hardware which drains the store buffer detects a store to a cache line which is not in the cache, then the cache line must be read into the cache before storing the updated data into the cache. These RFO reads have a longer latency when accessing remote DRAM over CXL. The model for CXL slowdown due to store buffer stalls is: k store is one of the pre-trained (platform-specific) model weights. is the value of a performance counter on Intel CPUs which counts the number of cycles where the store buffer is full. is simply the total number of cycles that the application ran for. Demand read stalls occur when a memory load instruction misses in the cache. The term “demand” refers to explicit memory load instructions, not prefetching. Cache misses due to loads are more complicated to model than cache misses due to stores. Processors have hardware to exploit memory level parallelism (multiple load misses outstanding at once), but the effectiveness of that hardware depends on the particular application code being run. Pointer chasing is the classic example of a workload with low memory level parallelism. The model for CXL slowdown due to demand read stalls is: k drd , , and are pre-trained weights. is a PMU counter which counts the number of cycles that the processor stalled due to a demand load that caused an L3 miss. is a PMU counter which counts the number of demand read requests sent to the uncore (L3 or off-chip memory). is a PMU counter which counts the total number of cycles where a demand read sent to the uncore was pending. The first term models what percentage of time the application could possibly be bound by memory. The second term models how much memory level parallelism is available in the application, and how much of that parallelism the hardware can exploit. The line fill buffer (LFB) is a hardware structure that tracks outstanding L1 cache misses (due to explicit loads or prefetch operations). When an L1 cache miss or prefetch occurs, an entry in the LFB tracks the pending load. When a subsequent load operation occurs that would normally trigger an L1 miss, the processor first checks the LFB to see if there is already a pending request to load the associated cache line. When the LFB fills up, then cache misses cause the processor to stall. The paper has separate models for CXL slowdowns due to LFB overutilization for different Intel chips. Here is the model for Skylake: I abbreviated the PMU counter names in the equation above: As usual, k cache is a platform specific constant, and measures total clock cycles. The first term models the percentage of time the workload is likely to be affected by increased memory latency. It is computed as the percentage of clock cycles when there was an L1 data miss but no L2 miss. The second term measures average utilization of the LFB. It is computed as a ratio of hits in the LFB divided by total operations that do not hit in the L1. The final term measures the percentage of LFB utilization that is attributable to prefetch operations. It is computed as the percentage of L1 prefetch operations which were satisfied by the L3. Fig. 1 shows how well various metrics predict the slowdown associated with moving a workload to CXL memory. The beautifully straight line in the rightmost chart shows that CAMP is a very accurate predictor. Source: https://dl.acm.org/doi/10.1145/3779212.3790201 Dangling Pointers This paper is a marvel of feature engineering, but do we not live in the era of deep learning? Subscribe now Slowdowns due to store buffer stalls Slowdowns due to demand read stalls Slowdowns due to line fill buffer (LFB) utilization

Hardware Performance

▲ 0

0 views

Dangling Pointers 4 months ago

Enabling Fast Networking in the Public Cloud

Enabling Fast Networking in the Public Cloud Alireza Sanaee, Vahab Jabrayilov, Ilias Marinos, Farbod Shahinfar, Divyanshu Saxena, Gianni Antichi, and Kostis Kaffes ASPLOS'26 Networking applications that care about latency don’t bother with the Linux networking stack. Instead they use a kernel-bypass library for fast networking (e.g., mTCP , libvma , TAS ). This paper points out two problems with using this approach on cloud VMs: Many of these libraries are not widely supported on cloud VMs, because cloud service providers want to expose a uniform feature set across a diverse set of server configurations The options that do work in the cloud (e.g., DPDK) assume a single process owns the NIC, which doesn’t work if there are multiple processes per VM that want to use low-latency networking This paper proposes Machnet, which is built around a user space sidecar process. As shown in Fig. 2, applications that want low-latency networking communicate with the sidecar process, and the sidecar uses DPDK to communicate with the virtual NIC exposed by the cloud service provider: Source: https://dl.acm.org/doi/10.1145/3779212.3790158 Each application uses multiple receive/transmit queue pairs in shared memory to communicate with the sidecar process. The sidecar comprises multiple CPU threads, each of which uses a dedicated receive/transmit queue pair to communicate with the NIC. Machnet is all about optimizing latency, not throughput. This justifies Machnet’s lack of zero-copy support. The really interesting bit is the mapping between application queues and sidecar queues. Say there is an HTTP server powered by 8 threads, each with its own queue pair and set of connections. Also assume the sidecar process uses 4 threads to communicate with the NIC. To avoid packet reordering within a connection, all packets from a particular HTTP server thread map to a single sidecar thread. This mapping is configured by applications. When a queue is created to communicate with the sidecar, the application specifies which sidecar thread (i.e., NIC queue) it should be associated with. What happens when the NIC receives a packet? Ideally that packet would make its way to the desired queue without expensive synchronization between the sidecar threads. If the sidecar had bare-metal access to a particular NIC, then it could configure the RSS settings of the NIC to map packets for a specific connection to the correct NIC queue. However, this level of RSS configuration is not broadly available to software running in cloud VMs. To work around this problem, the authors came up with RSS--. The authors found that opaque RSS is broadly supported. This means that the NIC can hash various fields from a packet header to determine which receive queue to route the packet to, but the hashing function is undocumented and unconfigurable. The authors leverage this support by giving the Machnet sidecar process flexibility in which ports are used for a given connection. When a new connection is set up, Machnet tries out a bunch of different source/destination ports, hoping that the NIC RSS hashing function will map one of them to the desired NIC receive queue. Section 4.2.1 has back-of-the-envelope math to say that trying out 47 different combinations is likely enough. Note that this scheme requires that Machnet is running on both sides of the connection. Once Machnet finds the magic combination of source/destination ports to use, it sticks with that combination for the connection and assumes the NIC will consistently route received packets to the correct NIC receive queue. With this magic in place, the sidecar threads can run at full speed without the need to synchronize with each other. Fig. 7 plots latency vs load for the standard Linux networking stack (labeled “HTTP…”) and Machnet. Lines labeled “Azure” were generated from runs in Azure VMs, lines labeled Cloudlab were generated on bare-metal servers. Machnet seems like a clear win. Source: https://dl.acm.org/doi/10.1145/3779212.3790158 Dangling Pointers The underlying issue here is a collective action problem. Once a standard like NVMe is widely adopted, then it becomes “table stakes” for cloud service providers. Clearly there is value in an industry standard for low-latency networking between cloud VMs, but how to achieve that standardization? Subscribe now Many of these libraries are not widely supported on cloud VMs, because cloud service providers want to expose a uniform feature set across a diverse set of server configurations The options that do work in the cloud (e.g., DPDK) assume a single process owns the NIC, which doesn’t work if there are multiple processes per VM that want to use low-latency networking

Cloud Performance

▲ 0

0 views

Dangling Pointers 4 months ago

Cicada: Dependably Fast Multi-Core In-Memory Transactions

Cicada: Dependably Fast Multi-Core In-Memory Transactions Hyeontaek Lim, Michael Kaminsky, and David G. Andersen SIGMOD'17 This paper is nine years old, but Gemini tells me it is still the state-of-the-art for single server, in-memory OLTP. Leave a comment if you know of a newer result. Section 3 of the paper describes three design principles for the Cicada database: Optimistic concurrency control Multi-versioning Loosely synchronized clocks Cicada stores multiple versions of each tuple in the database (each write produces a new version). As shown in Fig. 2, each tuple is stored as a linked list of versions: Source: https://dl.acm.org/doi/10.1145/3035918.3064015 Inlining is an important optimization described by the paper. The head node of each linked list can optionally store the data for the most recently generated version, which avoids pointer chasing on the common path. Each list element contains two timestamps. is the write timestamp, is a read timestamp. Each list is sorted such that the first list element is the most-recently-committed version. Cicada transactions do not use locks. Instead, Cicada optimistically assumes that no conflicts will occur and validates that assumption using the timestamps associated with each tuple accessed by a transaction. Per-version timestamps are also used to garbage collect old versions. The authors clearly put a lot of effort into scalable timestamp generation. A naive approach would be a single shared variable that is atomically incremented on each transaction. Contention for the cache line holding that variable would be nasty. Instead, Cicada uses loosely synchronized per-core clocks. Before starting a new transaction, a core uses the instruction to measure how much time has elapsed since the last transaction. This elapsed time is used to increment a local clock variable, which is used to generate the transaction timestamp. The least significant bits of each timestamp contain the ID of the thread which generated the timestamp (to ensure that all timestamps are unique). is not architecturally guaranteed to generate perfectly synchronized results across cores. Cicada compensates for unsynchronized clocks with periodic one-sided synchronization. Periodically, a core will compare the value of its local clock variable with the clock variable of another core. If the remote core has a larger value, then the local core will realize that it has a slow clock and will adjust accordingly to catch up. Cicada does not require perfect synchronization for correctness. If one clock is running slowly, its transactions will simply be more likely to abort. Fig. 3 shows TPC-C results. While Cicada supports durability with redo logging, these results were generated with logging disabled: Source: https://dl.acm.org/doi/10.1145/3035918.3064015 I find the 1 warehouse case to be the most interesting, as it has the most contention. Write contention clearly limits scalability even with all of the careful tuning to Cicada. Fig. 3(a) saturates at about 300K transactions per second for 8 cores. Back-of-the-envelope, that gives each core roughly 50,000 clock cycles to execute each transaction. TPC-C transactions aren’t that meaty. What is the speed of light? Subscribe now Optimistic concurrency control Multi-versioning Loosely synchronized clocks

Performance Database

▲ 0

0 views

Dangling Pointers 4 months ago

Beyond Page Migration: Enhancing Tiered Memory Performance via Integrated Last-Level Cache Management and Page Migration

Beyond Page Migration: Enhancing Tiered Memory Performance via Integrated Last-Level Cache Management and Page Migration Hwanjun Lee, Minho Kim, Yeji Jung, Seonmu Oh, Ki-Dong Kang, Seunghak Lee, and Daehoon Kim MICRO'25 This paper describes a complement to page migration to optimize performance on systems with tiered memory (a.k.a. a far pool of memory accessible over CXL ). State-of-the-art techniques for optimizing tiered memory systems involve classifying all pages as “hot” or “cold”. Hot pages are placed in the low-latency memory tier while cold pages are placed in a tier with higher access latency. Some systems dynamically measure hotness others try to predict it up front. The main point of this paper is that this bimodal hot/cold assumption may not always hold. What if no page is particularly hot or cold, but all are warm? Fig. 1 has some data to back this up. The bars labeled represent a system where pages are spread across both memory tiers. The bars labeled represent a system where pages are dynamically migrated based on their hotness. Interleaving utilizes more of the aggregate memory bandwidth. Source: https://dl.acm.org/doi/10.1145/3725843.3756063 LLC Partitioning This paper describes a system called . At its core, doesn’t migrate pages at all. Instead, it adjusts the fraction of the LLC that is dedicated to far cache lines. Fig. 4 illustrates the design of (hardware and software): Source: https://dl.acm.org/doi/10.1145/3725843.3756063 The hardware module measures average L1 miss latency for accesses to near and far memory. The adjusts the fractions of LLC ways that are available for caching near and far memory, in an attempt to balance the L1 miss latency for near and far accesses. For example, if the average L1 miss latency for far pages is higher than for near pages, then more LLC ways will be dedicated for caching far memory accesses. If the hardware is able to achieve balanced near and far L1 miss latencies, then the job is done. If not, then the hardware signals to the kernel that it should migrate pages based on measured hotness. Fig. 6 has simulated performance results. represents the core LLC allocation scheme while allows page migration as well. It is impressive that without page migration can beat other page migration schemes. This isn’t just a cherry on top, but a whole new way of looking at the problem. Source: https://dl.acm.org/doi/10.1145/3725843.3756063 Dangling Pointers Section 3 of the paper goes into some detail about how data cache prefetching helps hide far memory latency. It would be interesting if the system could decide which pages are likely to contain data for which the latency can be hidden. Subscribe now

Hardware Performance

▲ 0

0 views