So far, our circuit simulation has been running sequentially. In this session, we'll work on parallelizing the code. This will require us to do two things. First, we must describe how regions are partitioned (decomposed into pieces), so that Regent can determine what portions of the computation may run in parallel. Second, we'll need to update the tasks to use these newly partitioned regions.
Let's start with partitioning.
Partitioning is critical in Regent for two reasons. First, partitioning determines what data parallelism is available in the application (if any). Second, partitioning limits the amount of data movement required to perform a computation. Therefore, it will be important to think carefully about the access patterns (read and write sets) of each task in order to construct a good partitioning.
Generally speaking, we'll start by creating an initial independent partition of the data (i.e. a partition which does not depend on other partitions). We can make this partition intelligent by, for example, running METIS and partitioning based on the result. But for this exercise, we'll assume that a simple equal partition will suffice. An example of such a partition might look like this:
|
Equal Partition of Nodes
|
Now, if the application required no communication between tasks, this might be the only partition we would need. However, the circuit simulation requires communication: updates to nodes in the graph generally require access to the values stored on adjacent nodes. Conceptually, we could solve this by taking the partition above and bloating it by one node in each direction. But this could be really inefficient, because it would require the runtime to move much more data than actually required for the computation. Critically, the only data that must move is data for nodes connected to nodes of a different color.
This requires the use of dependent partitions (i.e. partitions computed from other partitions). With the preimage operator, we can obtain a partition of edges where each edge has the color of its in_node field (shown on the left, below). Then we can use the image operator to follow the out_node field back to nodes (shown in the center, below). Note in particular that nodes marked with multiple colors are exactly the nodes which will be involved in communication. With a little more work, we can obtain a partition of crossing nodes (shown on the right, below).
|
Preimage (Partition of Wires)
|
Image (Partition of Nodes)
|
Crossing (Partition of Nodes)
|
With this in mind, we can now compute three new partitions (which will actually be used directly in the application):
|
Private (Partition of Nodes)
|
Shared (Partition of Nodes)
|
Ghost (Partition of Nodes)
|
When take all nodes of a color (e.g. red) together, you'll see that they correspond to the bloated set of nodes required for task (as we noted above). However (and this is important for performance) only the shared and ghost partitions must be communicated. The private partition is non-overlapping with the other two, and thus it can safely stay put for the duration of the simulation.
Your goal is to construct the four partitions above (private, shared and ghost nodes, and wires). You may find it helpful to construct several intermediate partitions, such as the image, preimage, and crossing partition above. (Note that there are multiple valid solutions; your intermediate partitions might look different from those above.) We have given you an initial equal partition of the nodes to help you get started.
In [ ]:
partition(equal, R, ispace(int1d, N)) -- Divide R into N roughly even pieces.
partition(R.F, ispace(int1d, N)) -- Partition R according to the field R.F.
image(R, P, R2.F) -- Image over P via the field R2.F. Result is a partition of R.
preimage(R, P2, R2.F) -- Preimage of P via the field R2.F. Result is a partition of R.
P1 & P2 -- Intersection of partitions P1 and P2.
P1 | P2 -- Union of partitions P1 and P2.
P1 - P2 -- Difference of partitions P1 and P2.
In [ ]:
import "regent"
local c = regentlib.c
struct Currents {
_0 : float,
_1 : float,
_2 : float,
}
struct Voltages {
_1 : float,
_2 : float,
}
fspace Node {
capacitance : float,
leakage : float,
charge : float,
voltage : float,
}
fspace Wire(rn : region(Node)) {
in_node : ptr(Node, rn),
out_node : ptr(Node, rn),
inductance : float,
resistance : float,
capacitance : float,
current : Currents,
voltage : Voltages,
}
local CktConfig = require("session1/circuit_config")
local helper = require("session1/circuit_helper")
local validator = require("session2/circuit_partition_validator")
task toplevel()
var conf : CktConfig
conf:initialize_from_command()
conf:show()
var num_circuit_nodes = conf.num_pieces * conf.nodes_per_piece
var num_circuit_wires = conf.num_pieces * conf.wires_per_piece
var rn = region(ispace(ptr, num_circuit_nodes), Node)
var rw = region(ispace(ptr, num_circuit_wires), Wire(rn))
new(ptr(Node, rn), num_circuit_nodes)
new(ptr(Wire(rn), rw), num_circuit_wires)
c.printf("Generating a random circuit...\n")
helper.generate_random_circuit(rn, rw, conf)
-- This initial partition of nodes should be the basis of other partitions.
var colors = ispace(int1d, conf.num_pieces)
var pn_equal = partition(equal, rn, colors)
-- TODO: Compute the following partitions of nodes.
var pn_private
var pn_shared
var pn_ghost
-- TODO: Compute the partition of wires.
var pw
-- Put back this call if you want to print out the graph.
-- helper.dump_graph(conf, rn, rw)
-- Your partitions should pass this validation.
-- For each node and wire, validator checks if it belongs to a right region.
c.printf("Validating your circuit partitions...\n")
validator.validate_partitions(conf, rn, rw,
pn_private, pn_shared, pn_ghost, pw)
end
regentlib.start(toplevel)