## 4 Approach
### Simulator  
If all the parallel strategies were run in a real distributed environment, a large-scale cluster and considerable time would be needed. Therefore, Trinity introduces a simulator, which can simulate a parallel strategy without relying on real distributed environments.  
In the beginning, the parallel strategy will be executed in a real distributed environment to collect the running performance of the model on all devices. Then, the simulator will take over the real distributed environment, and predict the training time by computing the linear relationship between the computation costs \(E_{i}\) and the communication costs \(C_{i}\).  
The design of the simulator follows these three principles: (1) per-device \(d\) FIFO queues hold runnable operations; (2) communication overlaps with computing; and (3) operators which on the same devices should be executed serially. The simulator workflow is shown in Figure 3.  
The simulator maintains two first-in-first-out queues for each device in a dual-threaded manner and generates a time pipeline through a trigger mechanism which mainly includes three key processes: operator execution, tensor communication, and status checking. For the convenience of the explanation, let \(Q_{d}^{run}\) denote the operator execution queue on device \(d\), and record the sequence of operators to be run. Then, let \(Q_{d}^{com}\) denote the tensor queue that will communicate from device d to the other devices. This forms the collection of tensors. The details of the three key processes are as follows.  
1. Operator Execution  
The operator \(o_{i}\) to be executed from the queue \(Q_{d}^{run}\) is fetched, the operation is completely executed and the output is processed, as the execution in Figure 3. First, operation \(o_{i}\) is dequeued from the local execution queue \(Q_{d_{k}}^{run}\) to be executed. Second, all operators connected to the operator \(o_{i}\), denoted as \(o_{j}\), are obtained, and the device \(d_{l}\) where node \(o_{j}\) is checked. If \(d_{j}\
eq d_{i}\), the output tensor \(t_{i}\) of \(o_{i}\) is enqueued to \(Q_{d_{k}}^{com}\), and if \(d_{j}=d_{i}\), whether \(o_{j}\) meets the execution principle is checked, and if it is, it is enqueued to \(Q_{d_{k}}^{run}\). Finally, the status of \(Q_{d_{k}}^{run}\) is checked. If it is empty, trigger the idle state of device \(d_{k}\); and if not, dequeue the next operation from \(Q_{d_{k}}^{run}\) to execute. The detail of operator execution is described in Algorithm 2.  
2. Tensor Communication  
After tensor \(t_{i}\) communication is completed, other operators that depend on the current tensor are processed, as the execution in Figure 3. First, dequeue tensor \(t_{i}\) from the communication queue \(Q_{d_{k}}^{com}\) to communicate. Second, obtain all operators \(o_{k}\) that depend on \(t_{i}\), and check whether it is ready to start with the operating principle. If it is ready, put it into queue \(Q_{d_{k}}^{run}\). Finally, judge whether \(Q_{d_{k}}^{com}\) is empty. If it is empty, the communication triggering the state of device \(d_{k}\) is idle. If not, this process is cyclically executed.  
3. Status Check  
Judge whether \(Q_{d}^{run}\) and \(Q_{d}^{com}\) are empty. If they are empty, the idle state will be triggered; and if they are not empty, they will immediately dequeue to execute the operator execution or conduct tensor communication.  
```
Data:\(\mathcal{G}(O,E)\), \(\mathcal{D}\), \(Q_{d_{k}}^{run}\), \(Q_{d_{k}}^{com}\) Result: None initialization; whileTRUEdo \(\text{dequeue}(Q_{d_{k}}^{run})\); \(\text{run}(o_{i},d_{k})\); \(\text{operations}=o_{i}.\text{depend}()\); for\(o_{j}\)in operationsdo if\(o_{j}.\text{dequeue}()\
eq d_{i}\):then \(Q_{d_{k}}^{com}.\text{push}(o_{i}.\text{outputs}())\) elseif\(o_{j}.\text{device}()==d_{i}\)and\(o_{j}.\text{canRun}()\)then \(Q_{d_{k}}^{run}.\text{enqueue}(o_{j})\)  end if  end while
```  
**Algorithm 2**Operator Execution (\(o_{i}\) executes on \(d_{k}\)).