Advanced Routing Algorithms for General Purpose Photonic Processors

Directional couplers/ MZIs acting as the routers in a general purpose photonic processors (GPPPs) form the fundamental unit of the circuit and can be represented using a directed or undirected bipartite graph as shown in Figure 1a. These MZIs can stay either in a cross or bar, or tunable state and conventional graph search algorithms can be employed to find the paths between the nodes of an individual MZI or a connected network of MZIs. However, searched path will consist of both physical and nonphysical paths. For example, two paths obtained between node ’a’ and ’c’ are: ’a’-’c’, which is a physical path and ’a’-’d’-’b’-’c’, which is a nonphysical path as back reflected paths are not allowed/considered in optical devices. Also, an MZI, if assigned a particular state (bar or cross) after searching a path, must remain in the same state for another path as well while searching multiple paths in a network. This is called the bar cross condition. Thus, various methods can be employed to eliminate the nonphysical paths and simultaneously maintaining the bar cross condition while designing the network and algorithms [19], [20]:

1. 1.

   The algorithm can be modified such that same device cannot be accessed twice in a path by setting the maximum number of nodes traversed for same device to 2. This method works fine for finding the shortest path but fails to detect the cycles and paths with the desired length (number of MZIs) in the network.

2. 2.

   The network can be implemented using directed graphs, in this case two layered graphs are needed for accessing the network from both the directions, one for each direction. Also, every time a path is found in any direction, it needs to be engaged in the other layer, to avoid contradictory assignment of states of MZIs while searching multiple paths in a network. It increases the space and time complexity of the path searching algorithms.

3. 3.

   Another method is to include the dummy nodes with large negative weights at both the inputs and outputs as shown in Figure 1b. In this case if any nonphysical path is encountered the weight will grow large, and for a physical path the total weight for each traversed unit will be 1. It doubles the space complexity of the graph as compared to simple bipartite graph but increases the accuracy of path search algorithm.

Penalties such as delay, insertion loss and power consumption can be added as edge weights in each unit while applying any of the above mentioned solutions, and algorithms can be modified to optimize any of these penalties either one at a time or simultaneously.

Given the advantages of hexagonal topology, the hexagonal arrangement of MZIs is utilized to implement the GPPP architecture. The fundamental unit (MZI) is defined using the dummy nodes as shown in Figure 1b. Here large negative and positive weights are allocated to the edges connecting the dummy nodes and primary nodes, respectively. As a result of this allocation, the total weight for a physical path (eg: ’e’-’a’-’c’-’g’, ’e’-’a’-’d’-’h’) in the MZI becomes 1, whereas the weight for a nonphysical path (eg: ’e’-’a’-’d’-’b’-’c’-’g’, ’e’-’a’-’c’-’b’-’d’-’h’) becomes 4003. Based on these allocations, as soon as a node of a nonphysical path is encountered in the search algorithm, the total weight becomes $>=3002$. Thus a threshold weight can be assigned for eliminating nonphysical paths in search algorithms. MZIs are arranged across an inner and outer circle to form a unit cell, as shown in Figures 2a and 2b, respectively. Nodes of MZIs along the inner and outer circles are named using ’i’ and ’o’, respectively. A unit cell is formed by combining the two circular arrangements as shown in Figure 2c. To implement a multi-cell network, the number of cells required in the network is entered through an input prompt, based on which cells are distributed around the central cell. The Centre positions of these cells are calculated using inner and outer circle radii. Unit cells formed at their respective positions are added to the network, and overlapping nodes between the cells are found and deleted from one cell while connecting the individual cells, as shown in Figure 3. Nodes are numbered according to the cell number starting from 0 for the central cell. For example, a node at the inner MZI at a position ’r’ in the cell ’q’ is represented as ’ixrq’ where ’x’ can take alphabets between ’a’ and ’h’ (referring to fundamental unit’s node). Position of each node is saved in a list corresponding to its cell and updated every time a node is added or deleted in the network. A 5-cell and an 11-cell network with 36 and 70 MZIs, respectively are prepared for implementing path and cycle search algorithms.

The bidirectional search algorithm is a BFS based algorithm utilized to find the shortest path in a graph. In this algorithm, two simultaneous searches are performed step by step, one in the forward direction initiating from the start node and another in the backward direction, initiating from the target node, while adding weights at each node. Two visited dictionaries are maintained for search in both directions, and nodes visited in forward and backward searches are added to these dictionaries. To eliminate the nonphysical paths, a condition is added to the search algorithm, and a new node is added to the dictionary only if the weight at that node is smaller than the threshold weight and is not in the visited list. An intersection search is employed in each search step to find the intersection between the two dictionaries. If an intersection is found, the path between the start and target node is created from the intersecting node using predecessors and successors in the forward and backward visited dictionaries, respectively, and the total weight is calculated alongside the path. However, this algorithm works well with non-cyclic simple graphs but poses a problem with cyclic or complex graphs.

DFS is a recursive algorithm that finds all the paths between a source and a target node. It can also be employed to search the path of a given weight in the network by simple modification in the return condition. Search starts from the source node and recursively calls the searching function at each neighbouring node. A visited set is maintained, holding the nodes being visited and a weight set is created to hold the weight at the current node, which is updated at each searched node. To eliminate the nonphysical paths threshold weight condition is added to the recursive calling loop such that the node is added to the search only if the total weight at the node is less than the threshold and is not in the visited list. Otherwise, the search returns to the previous node, thus eliminating the nonphysical path simultaneously while searching. If the current and target nodes are the same, then a path with respective weight is returned and added to the list of paths.

DFS algorithm performs path search with higher accuracy and speed in complex and cyclic graphs. As DFS is a recursive algorithm in order to stop the search, it needs to come out of all the loops that the algorithm had run step by step, returning to the nodes it has gone through previously. For DFS to return the shortest path, the algorithm is modified such that once the first path is searched and stored in the path variable along with its weight, the algorithm will check the path weight at each new node. If the weight exceeds the weight of the path previously searched, it will not search further from that node and return to the previous node, and if the weight is smaller than the stored weight, it will carry the search either until the target node is found or weight exceeds the saved weight. Thus, if a new path with a smaller weight is found, the path is updated with the new path alongside its weight.

A similar modification is also applied to search a path with a given weight. In this case, the first path is updated only when a path with the required weight is found. In order to return the path, recursive calling is stopped by continuously returning the path until return functions roll back to the first node where the calling started.

However, BFS and Bellman-Ford algorithms support the cyclic graph, but a negative cycle graph limits them. Thus, a recursive search algorithm with a concept similar DFS is employed to implement the cycle search algorithm. A visited and total weight set is created and updated on successful search at each node. Here a parent node is added, and a recursive search is called at each node starting from the parent node. Search at a node progresses if the threshold weight condition is met and the node is not in the visited list, like DFS. If the current node is in the visited list and is the same as the parent node, then a cycle with the respective weight is added to the cycle’s list. Otherwise, the search returns to the previous node, simultaneously eliminating nonphysical cycles. To find the shortest and fixed length cycles return conditions are modified using the concept used in section 3.3

For searching the shortest path between a pair of source and a target, modified bidirectional search and modified DFS algorithms are employed. A path between nodes ’of33’ and ’of01’ is found where the total number of travelled units was 9, and the time taken to search the path using the modified bidirectional search was 1.17 ms. The same path was searched using modified DFS in 5.74 ms. Figures 4a and 4b shows two paths searched between source-target pairs ’oe23’ and ’of42’ (and ’oe33’ and ’of01’). Although the modified bidirectional search algorithm is faster than the modified DFS while searching the shortest path, it fails while accessing parallel nodes of the same unit as input and output, as shown in Figure 4c (marked in red oval). An intersection is found at the node ’oe0’, which is the corner node of MZI. Paths are created from this node, we can see both paths in the forward and backward direction from the source, and target nodes are physical, but the overall path is nonphysical. This problem is not encountered in modified DFS, shown in Figure 4d. Mean exectuion time for DFS shortest path search algorithm for 5-cell and 11-cell networks were calculated to be 7.16 ms and 88 ms, respectively. A 7-cell architecture similar to ones reported is [20] was also analyzed and the mean execution time for DFS shortest search was 7.52 ms.

DFS search is also employed for finding all the existing physical paths between a pair of source and target. Case I in Figure 5a shows the path existing between the two parallel nodes of the same unit, ’of3’-’oe3’ in a 3 unit cells network. A total of 20 paths were found, time taken to find these paths was 4 ms figure shows 3 of these paths with weights of 8 (red), 8 (green) and 12 (violet). In case II, shown in Figure 5b, paths were found between ’of33’ and ’oe21’. A total of 484 paths with weights ranging from 7 to 33 were found, and the time taken to search these paths was 218.3 ms. The Figure shows 3 of these paths with weights of 7 (orange), 11 (green) and 33 (violet). Mean execution time to search paths over different source target pairs in a 5-cell network was 220 ms.

Due to higher accuracy, modified DFS is employed to find the shortest path between multiple source-target pairs. To prevent traversing of the same unit twice while path search and to maintain bar cross condition, the visited list is updated with the list of nodes engaged in the previous paths. Three different cases were taken for finding 4,6, and 7 paths between different pairs of source-target nodes in the network. In the first case, paths were found between ’of33’-’oe01’, ’oe33’-’of01’, ’of11’-’oe02’ and ’oe21’-’of02’, as shown in Figure 6a. The time taken to search these paths was 16.7 ms. Here we can observe that in comparison to the path found between the nodes ’oe33’-’of01’ in the single source-target shortest path case, the path found in this case is different. Since a path exists between the nodes ’of33’-’oe01’, an appropriate path is found to prevent violation of the bar and cross condition of the individual unit. In case II, paths were found between the nodes ’of33’-’oe01’, ’oe33’-’of01’, ’of11’-’of02’, ’oe21’-’oe02’, ’oe23’-’of42’ and ’of13’-’oe52’, as shown in Figure 6b. Here again, while comparing the paths obtained for the nodes ’oe23’-’of42’ in the single source-target shortest path and multi source-target shortest path, we can observe that instead of getting the shortest path as in the prior case, a path maintaining the bar and cross condition for individual units was found. The time taken to search 6 paths was 17.8 ms. Figure 6c shows case III, where paths are found between the nodes ’of33’-’oe01’, ’oe33’-’of01’, ’of11’-’of52’, ’oe21’-’oe42’, ’of34’-’oe02’, ’oe34’-’of02’ and ’oe13’-’oe54’. Here time taken to search 7 paths was 18.4 ms. To further evaluate the accuracy of the algorithm, another case of searching paths between 7 source-target pairs was taken. This case was run two times with different orders of source-target pairs. First order was ’oe23’-’of42’, ’of13’-’oe52’, ’of33’-’oe01’, ’oe33’-’of01’, ’oe21’-’oe02’, ’of11’-’oe52’ and ’of34’-’oe11’, and the second order was ’of33’-’oe01’, ’oe33’-’of01’, ’oe21’-’oe02’, ’of11’-’of02’, ’of34’-’oe11’, ’oe23’-’of42’ and ’of13’-’oe52’. Path obtained for the two cases are shown in Figures 6d and 6e, respectively. Since searching paths between multiple source-target pairs is a sequential process where paths are searched in the given order of source-target pairs, we can observe that for the first order, 5 paths were found out of 7; however, for second order, 6 paths were found out of 7. In all the paths found here, no nonphysical path or violation of the bar cross condition was observed, the algorithm returned empty if no physical path existed, which proves the accuracy of the algorithm. A 7 cell structure similar to one reported in [19], [20] have also been analyzed in 6f and execution time for searching 6 paths between ’of44’-’oe11’, ’oe33’-’oe02’, ’of111’-’of412’, ’of23’-’of01’, ’of211’-’of512’ and ’of34’-’of52’ was 18.5 ms. For the same network 8 paths were searched in the exectuion time of 19.1 ms.

The cycle search algorithm is employed to search all the cycles from a given parent node. The parent node is selected as the starting node of any MZI. Two cases, one for a smaller network of three cells and another for a larger network, are considered. For the case I shown in Figure 7a, all possible cycles with ’ih2’ as the parent node were searched, and ten cycles with weights ranging from 6 to 18 were found. The Figure shows two of these cycles with weights 6 (orange) and 10 (green). The network consists of 24 MZIs, and the time taken to search all the cycles was 7.56 ms. It is worth noting that while searching total of 20 cycles are found, accounting for search in both the directions from the parent and then cycles with the same nodes are removed. In case II, all the cycles were searched along the node ’ih33’ in the larger network, and 96 cycles with weights ranging from 6 to 30 are found. Figure 7b shows the cycles of weight 6 (orange) and 10 (green), and Figure 7c shows the cycle of weight 30. From the Figure, it is observed that no nonphysical path is traversed in any of the cycles, which proves the accuracy of the cycle search algorithm. Mean exectution time ofcycle search algorithm for various parent nodes was calculated to be 163.9 ms.