Electrical Engineering Systems Seminar

Speaker: Rami Zecharia

Ph.D. student under the supervision of Prof. Yuval Shavitt

Sunday, 30^th June 2024, at 15:00

Room 011, Kitot Building, Faculty of Engineering

Routing Algorithms in Benes and CLOS Networks

Abstract

Benes/CLOS architectures are common scalable interconnection networks widely used in backbone routers, data centers, on-chip networks, multi-processor systems, and parallel computers. Recent advances in Silicon Photonic technology, especially in Mach–Zehnder Interferometer (MZI) technology which is the building block for low-cost high-speed 2x2 optical switch, have made Benes networks a very attractive scalable architecture for optical circuit switches.
Numerous routing algorithms for Benes networks were developed starting with sequential routing algorithms with time complexity of O(Nlog₂N) steps and, in some cases, requires backtracking, which makes them even less efficient. Parallel routing algorithms were developed to satisfy the stringent timing requirements of high-performance switching networks and have time complexity of O((log₂N)²). However, their implementation requires O(N²log₂N) wires (termed connectivity complexity), and thus are difficult to scale. Online (Adaptive) routing algorithms do not utilize the re-arrangeable characteristics of a network as they establish a single path at a time without interrupting already established paths. Such online algorithms yield poor utilization, resulting in low throughput and high latency which impedes their usage.

In this thesis, we present three new and improved routing algorithms for Benes network:

• A parallel routing algorithm combined with a unique scalable hardware architecture that supports full and partial input permutations. The algorithm achieves close to 100% utilization for both full and partial input permutations. Time complexity is limited to O((log₂N)²) steps to match the performance of parallel algorithms. The algorithm and architecture allow a reduction of the connectivity complexity to O(N²), a log₂N improvement over previous solutions.
• An engineering approach to the already known sequential routing algorithm along with a unique scalable hardware architecture. The new algorithm supports full and partial input permutations with a significantly lower time complexity of O(N^3/5) and connectivity complexity of O(N²) and achieves 100% complete routing of a given full or partial input permutation with probability of 99.9999%. The achieved time complexity is comparable to parallel algorithms.
• An online (adaptive) routing algorithm achieving significant increase of utilization (number of established paths for a given input permutation) compared to prior work hence increased throughput and reduce latency while operating within the same time complexity as prior works, hence enabling the usage of Benes network based optical switches for a wide range of applications. We further applied this algorithm to CLOS network achieving even higher average utilization as compared to a single Benes network-based switch of the same size. Hence, enabling the usage of large-scale CLOS-based optical networks for various applications.

השתתפות בסמינר תיתן קרדיט שמיעה = עפ"י רישום שם מלא + מספר ת.ז. בדף הנוכחות שיועבר באולם במהלך הסמינר

סמינר זה יחשב כסמינר שמיעה לתלמידי תואר שני ושלישי

ההרשמה מתבצעת לפני תחילת הסמינר

חברת אנבידיה מגיעה לפגוש אתכם.ן בקמפוס

סטודנטים.ות יקירים ויקרות חברת אנבידיה מגיעה לקמפוס לפגוש אתכם ואתכן במפגש פתוח ומזמין.

מתי? 05.06.24 החל מהשעה 12:00

איפה? לובי בניין כיתות חשמל

מה בתוכנית? לאירוע יגיעו מיטב הצוותים של החברה, מהנדסים וגיוס, מוזמנים להגיע ולבנות לכם את מסלול הקריירה הבא בחברה.

נתראה

Electrical Engineering Systems Seminar

(The talk will be given in English)

Speaker:     Prof. Kfir Y. Levy

Electrical and Computer Engineering Department, Technion

011 hall, Electrical Engineering-Kitot Building

Monday, June 10^th, 2024

12:00-13:00

Do Stochastic, Feel Noiseless: Stable Optimization via a Double Momentum Mechanism

Abstract

The tremendous success of the Machine Learning paradigm heavily relies on the development of powerful optimization methods, and the canonical algorithm for training learning models is SGD (Stochastic Gradient Descent). Nevertheless, the latter is quite different from Gradient Descent (GD) which is its noiseless counterpart. Concretely, SGD requires a careful choice of the learning rate, which relies on the properties of the noise as well as the quality of initialization. It further requires the use of a test set to estimate the generalization error throughout its run. In this talk, we will present a new SGD variant that obtains the same optimal rates as SGD, while using noiseless machinery as in GD. Concretely, it enables to use the same fixed learning rate as GD and does not require to employ a test/validation set. Curiously, our results rely on a novel gradient estimate that combines two recent mechanisms which are related to the notion of momentum. Finally, as much as time permits, I will discuss several applications where our method can be extended.

Short Bio

Kfir Y. Levy is an Assistant Professor in the Electrical and Computer Engineering Department at Technion – Israel Institute of Technology. Kfir’s research is focused on Machine Learning, AI, and Optimization, with a special interest in designing universal methods that apply to a wide class of learning scenarios. Kfir did his postdoc in the Institute for Machine Learning at ETH Zurich. He is a recipient of the Alon fellowship, the ETH Zurich Postdoctoral fellowship, as well as the Irwin and Joan Jacobs fellowship. He received all of his degrees from the Technion.

השתתפות בסמינר תיתן קרדיט שמיעה = עפ"י רישום שם מלא + מספר ת.ז. בדף הנוכחות שיועבר באולם במהלך הסמינר